2025-11-17T07:58:12.711519

Posterior Sampling for Continuing Environments

Xu, Dong, Van Roy
We develop an extension of posterior sampling for reinforcement learning (PSRL) that is suited for a continuing agent-environment interface and integrates naturally into agent designs that scale to complex environments. The approach, continuing PSRL, maintains a statistically plausible model of the environment and follows a policy that maximizes expected $γ$-discounted return in that model. At each time, with probability $1-γ$, the model is replaced by a sample from the posterior distribution over environments. For a choice of discount factor that suitably depends on the horizon $T$, we establish an $\tilde{O}(τS \sqrt{A T})$ bound on the Bayesian regret, where $S$ is the number of environment states, $A$ is the number of actions, and $τ$ denotes the reward averaging time, which is a bound on the duration required to accurately estimate the average reward of any policy. Our work is the first to formalize and rigorously analyze the resampling approach with randomized exploration.
academic

निरंतर वातावरण के लिए पश्च नमूनाकरण

मूल जानकारी

  • पेपर ID: 2211.15931
  • शीर्षक: निरंतर वातावरण के लिए पश्च नमूनाकरण
  • लेखक: वानकियाओ जू (स्टैनफोर्ड विश्वविद्यालय), शि डोंग (गूगल डीपमाइंड), बेंजामिन वैन रॉय (स्टैनफोर्ड विश्वविद्यालय)
  • वर्गीकरण: cs.LG stat.ML
  • प्रकाशन सम्मेलन: RLJ | RLC 2024
  • पेपर लिंक: https://arxiv.org/abs/2211.15931

सारांश

यह पेपर निरंतर वातावरण के लिए एक पश्च नमूनाकरण सुदृढ़ीकरण सीखने का एल्गोरिदम (Continuing PSRL) प्रस्तावित करता है, जो स्केलेबल एजेंट डिजाइन में स्वाभाविक रूप से एकीकृत हो सकता है। एल्गोरिदम एक सांख्यिकीय रूप से उचित वातावरण मॉडल बनाए रखता है और एक ऐसी नीति का पालन करता है जो इस मॉडल में γ-छूट प्राप्त रिटर्न को अधिकतम करता है। प्रत्येक समय चरण पर, एल्गोरिदम संभावना 1-γ के साथ वातावरण के पश्च वितरण से मॉडल को पुनः नमूना करता है। समय सीमा T पर निर्भर छूट कारक के उपयुक्त चयन के माध्यम से, Õ(τS√AT) की बेयेसियन पश्चाताप सीमा स्थापित की गई है, जहां S वातावरण की स्थिति संख्या है, A क्रिया संख्या है, और τ पुरस्कार औसत समय को दर्शाता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मुख्य समस्या

मौजूदा पश्च नमूनाकरण सुदृढ़ीकरण सीखने के एल्गोरिदम मुख्य रूप से एपिसोडिक वातावरण के लिए डिज़ाइन किए गए हैं, जो स्थिति-क्रिया पहुंच गणना को बनाए रखने पर निर्भर करते हैं, जिससे वे उच्च-आयामी स्थिति स्थान वाले जटिल निरंतर वातावरण के लिए अनुपयुक्त हैं।

समस्या की महत्ता

  1. निरंतर वातावरण सीखना सुदृढ़ीकरण सीखने में एक मौलिक समस्या है, लेकिन मौजूदा यादृच्छिकीकरण अन्वेषण विधियां मुख्य रूप से एपिसोडिक वातावरण तक सीमित हैं
  2. स्केलेबिलिटी आवश्यकता: पारंपरिक विधियां स्थिति-क्रिया पहुंच गणना पर निर्भर करती हैं, जो जटिल वातावरण में व्यावहारिक नहीं है
  3. सैद्धांतिक अंतराल: निरंतर वातावरण के लिए कठोर सैद्धांतिक विश्लेषण की कमी

मौजूदा विधियों की सीमाएं

  1. TSDE (Ouyang et al., 2017): जटिल पुनः नमूनाकरण मानदंड की आवश्यकता है, जिसमें पहुंच गणना दोहरीकरण शर्तें शामिल हैं, जो बड़ी स्थिति स्थान में व्यावहारिक नहीं है
  2. DS-PSRL (Theocharous et al., 2018): हालांकि पहुंच गणना से बचता है, लेकिन विश्लेषण मजबूत तकनीकी मान्यताओं पर निर्भर करता है, और इन मान्यताओं के बिना पश्चाताप सीमा रैखिक रूप से बढ़ती है
  3. पारंपरिक PSRL: केवल एपिसोडिक वातावरण के लिए उपयुक्त है, निरंतर सेटिंग में सीधे विस्तार नहीं कर सकता

अनुसंधान प्रेरणा

एक सरल, स्केलेबल और सैद्धांतिक रूप से कठोर निरंतर वातावरण पश्च नमूनाकरण एल्गोरिदम प्रस्तावित करना, जो:

  • स्थिति-क्रिया पहुंच गणना को बनाए रखने से बचता है
  • मौजूदा फ़ंक्शन सन्निकटन विधियों में स्वाभाविक रूप से एकीकृत होता है
  • मौजूदा सर्वोत्तम विधियों के साथ मेल खाने वाली सैद्धांतिक गारंटी प्रदान करता है

मुख्य योगदान

  1. पहला स्केलेबल निरंतर PSRL एल्गोरिदम: सरल यादृच्छिकीकरण योजना पर आधारित Continuing PSRL प्रस्तावित किया, जटिल पुनः नमूनाकरण मानदंड से बचा
  2. कठोर सैद्धांतिक विश्लेषण: Õ(τS√AT) की बेयेसियन पश्चाताप सीमा स्थापित की, जो मौजूदा सर्वोत्तम परिणामों से मेल खाती है
  3. स्केलेबिलिटी में सफलता: एल्गोरिदम उच्च-आयामी स्थिति स्थान और फ़ंक्शन सन्निकटन सेटिंग में स्वाभाविक रूप से विस्तारित हो सकता है
  4. छूट कारक का नया दृष्टिकोण: छूट कारक को एल्गोरिदम डिजाइन उपकरण के रूप में देखा, न कि वातावरण विशेषता के रूप में, छूट कारक की भूमिका को समझने के लिए नया दृष्टिकोण प्रदान किया

विधि विवरण

कार्य परिभाषा

एक अज्ञात वातावरण E = (A,S,ρ) द्वारा मॉडल किए गए मार्कोव निर्णय प्रक्रिया पर विचार करें, जहां:

  • A परिमित क्रिया स्थान है, |A| = A
  • S परिमित स्थिति स्थान है, |S| = S
  • ρ स्थिति संक्रमण संभावना फ़ंक्शन है
  • पुरस्कार फ़ंक्शन r : S × A → 0,1 निर्धारक और ज्ञात है

लक्ष्य संचयी पश्चाताप को कम करना है: Regret(T,π):=∑t=0T−1(λ∗,E−Rt+1)\text{Regret}(T,π) := \sum_{t=0}^{T-1}(λ_{*,E} - R_{t+1})

जहां λ_{*,E} इष्टतम औसत पुरस्कार है।

मॉडल आर्किटेक्चर

छद्म-एपिसोड निर्माण

एल्गोरिदम अनंत समय सीमा सीखने की समस्या को यादृच्छिक लंबाई के छद्म-एपिसोड में विघटित करता है:

  • प्रत्येक समय चरण t पर, बाइनरी संकेतक X_t नमूना करें
  • जब X_t = 0 हो, तो नया छद्म-एपिसोड शुरू करें और वातावरण मॉडल को पुनः नमूना करें
  • जब X_t = 1 हो, तो वर्तमान छद्म-एपिसोड जारी रखें

छूट मूल्य फ़ंक्शन

वातावरण E और नीति π के लिए, γ-छूट मूल्य फ़ंक्शन को परिभाषित किया जाता है: Vπ,Eγ:=E[∑h=0H−1Pπhrπ∣E]=E[∑h=0∞γhPπhrπ∣E]V^γ_{π,E} := \mathbb{E}\left[\sum_{h=0}^{H-1} P^h_π r_π | E\right] = \mathbb{E}\left[\sum_{h=0}^{∞} γ^h P^h_π r_π | E\right]

जहां H छद्म-एपिसोड की लंबाई है, जो ज्यामितीय वितरण का पालन करती है।

पुरस्कार औसत समय

मुख्य अवधारणा पुरस्कार औसत समय τ_{π,E} है, जिसे न्यूनतम τ के रूप में परिभाषित किया गया है जैसे कि: ∣Eπ[∑t=0T−1Rt+1∣E,S0=s]−T⋅λπ,E(s)∣≤τ\left|\mathbb{E}_π\left[\sum_{t=0}^{T-1} R_{t+1} | E, S_0 = s\right] - T \cdot λ_{π,E}(s)\right| \leq τ

एल्गोरिदम प्रवाह

एल्गोरिदम 1: Continuing PSRL

इनपुट: पूर्व वितरण f, छूट कारक γ, कुल सीखने का समय T
1. प्रारंभ करें t=1, k=1, X₁=0
2. for t ≤ T:
3.   if Xₜ = 0:
4.     tₖ ← t
5.     नमूना Eₖ ~ f(·|H_tₖ)
6.     गणना करें πₖ = π^γ_Eₖ
7.     k ← k+1
8.   नमूना और निष्पादित करें Aₜ ~ πₖ(·|Sₜ)
9.   अवलोकन करें Rₜ₊₁ और Sₜ₊₁
10.  t ← t+1
11.  नमूना Xₜ₊₁ ~ Bernoulli(γ)

तकनीकी नवाचार बिंदु

  1. सरल पुनः नमूनाकरण तंत्र: केवल बर्नौली यादृच्छिक संख्या जनरेटर का उपयोग करता है, जटिल पहुंच गणना शर्तों से बचता है
  2. छूट कारक और पुनः नमूनाकरण संभावना का संबंध: γ = 1-p सेट करें, जहां p पुनः नमूनाकरण संभावना है
  3. नीति-स्वतंत्र पुनः नमूनाकरण: पुनः नमूनाकरण मानदंड नीति से स्वतंत्र है, विश्लेषण को सरल करता है
  4. समय-परिवर्तनशील छूट कारक: छूट कारक को समय के साथ बढ़ने की अनुमति देता है, उप-रैखिक पश्चाताप प्राप्त करता है

प्रयोगात्मक सेटअप

डेटासेट

  1. तालिका-रूप RiverSwim वातावरण:
    • 6 स्थिति की श्रृंखला संरचना
    • बाएं छोर की स्थिति पुरस्कार 0.005, दाएं छोर की स्थिति पुरस्कार 1.0
    • इष्टतम नीति हमेशा दाईं ओर तैरना है
  2. निरंतर विशेषता RiverSwim वातावरण:
    • समान संरचना लेकिन पिक्सेल विशेषता अवलोकन का उपयोग करता है
    • विशेषता मानचित्रण: φ(s_t) = 1{x ≤ s_t} ∈ 0,1^N
    • फ़ंक्शन सन्निकटन सेटिंग में एल्गोरिदम प्रदर्शन का परीक्षण करें

मूल्यांकन मेट्रिक्स

  • संचयी पश्चाताप (Cumulative Regret)
  • समय के साथ औसत पश्चाताप में परिवर्तन

तुलना विधियां

  1. TSDE (Ouyang et al., 2017): पहुंच गणना पर आधारित थॉम्पसन नमूनाकरण
  2. DS-PSRL (Theocharous et al., 2018): निश्चित समय अंतराल पुनः नमूनाकरण योजना
  3. यादृच्छिक एजेंट: आधारभूत के रूप में
  4. DQN with ε-greedy: निरंतर विशेषता वातावरण में तुलना

कार्यान्वयन विवरण

  • पूर्व वितरण: डिरिचलेट वितरण (संक्रमण) और सामान्य-गामा वितरण (पुरस्कार)
  • हाइपरपैरामीटर: छद्म-गणना n=1, α=1/S, μ=σ²=1
  • निरंतर वातावरण में Bootstrapped DQN का उपयोग करें, γ=0.99

प्रयोगात्मक परिणाम

मुख्य परिणाम

  1. तालिका-रूप वातावरण:
    • Continuing PSRL TSDE के साथ तुलनीय प्रदर्शन करता है, हालांकि बाद वाला सीधे औसत पुरस्कार को अनुकूलित करता है
    • DS-PSRL से काफी बेहतर
    • सैद्धांतिक रूप से भविष्यवाणी की गई उप-रैखिक पश्चाताप वृद्धि को सत्यापित करता है
  2. निरंतर विशेषता वातावरण:
    • Bootstrapped DQN + यादृच्छिक पुनः नमूनाकरण उप-रैखिक पश्चाताप प्राप्त करता है
    • vanilla DQN with ε-greedy अन्वेषण से स्पष्ट रूप से बेहतर
    • जटिल वातावरण में विधि की स्केलेबिलिटी को साबित करता है

प्रयोगात्मक निष्कर्ष

  1. सरल पुनः नमूनाकरण की प्रभावशीलता: हालांकि पुनः नमूनाकरण तंत्र सरल है, लेकिन प्रदर्शन जटिल विधियों के साथ तुलनीय है
  2. स्केलेबिलिटी लाभ: उच्च-आयामी स्थिति स्थान में, पहुंच गणना पर निर्भर पारंपरिक विधियां विफल हो जाती हैं, जबकि यह विधि प्रभावी रहती है
  3. सिद्धांत और अभ्यास की सामंजस्य: प्रयोगात्मक परिणाम सैद्धांतिक विश्लेषण की सटीकता को सत्यापित करते हैं

संबंधित कार्य

थॉम्पसन नमूनाकरण और पश्च नमूनाकरण

  • शास्त्रीय थॉम्पसन नमूनाकरण: मूल रूप से बहु-सशस्त्र दस्यु समस्या के लिए उपयोग किया जाता है
  • PSRL विस्तार: ओसबैंड आदि ने इसे सुदृढ़ीकरण सीखने तक विस्तारित किया, लेकिन मुख्य रूप से एपिसोडिक वातावरण के लिए
  • Bootstrapped DQN: पश्च वितरण का अनुमान लगाने के लिए समूह विधि का उपयोग करता है

निरंतर वातावरण में अन्वेषण

  • TSDE: निरंतर वातावरण के लिए पहली थॉम्पसन नमूनाकरण विधि, लेकिन जटिल पुनः नमूनाकरण मानदंड पर निर्भर
  • DS-PSRL: पुनः नमूनाकरण को सरल किया लेकिन मजबूत तकनीकी मान्यताओं की आवश्यकता है
  • यह कार्य: पहली बार सरल और कठोर यादृच्छिक पुनः नमूनाकरण विधि प्रदान करता है

सैद्धांतिक विश्लेषण

  • मौजूदा कार्य अधिकतर γ-छूट पश्चाताप पर विचार करते हैं, यह कार्य बिना छूट पश्चाताप पर ध्यान केंद्रित करता है
  • पुरस्कार औसत समय τ का उपयोग पारंपरिक span अवधारणा को प्रतिस्थापित करता है
  • कमजोर जुड़ा हुआ MDP धारणा परिमित समय पश्चाताप सीमा के लिए सबसे सामान्य सेटिंग है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सैद्धांतिक योगदान: Õ(τS√AT) की पश्चाताप सीमा स्थापित की, जो मौजूदा सर्वोत्तम परिणामों से मेल खाती है
  2. एल्गोरिदम सरलता: केवल एक बर्नौली यादृच्छिक संख्या जनरेटर की आवश्यकता है प्रभावी अन्वेषण के लिए
  3. व्यावहारिक मूल्य: एल्गोरिदम मौजूदा गहरे सुदृढ़ीकरण सीखने की विधियों में सीधे एकीकृत हो सकता है
  4. छूट कारक नया दृष्टिकोण: छूट कारक को एल्गोरिदम डिजाइन उपकरण के रूप में देखता है, न कि वातावरण विशेषता के रूप में

सीमाएं

  1. सैद्धांतिक मान्यताएं: कमजोर जुड़ा हुआ MDP और बंधी हुई पुरस्कार औसत समय की मान्यताओं की आवश्यकता है
  2. पूर्व निर्भरता: प्रदर्शन उचित पूर्व वितरण सेटिंग पर निर्भर करता है
  3. पैरामीटर ट्यूनिंग: छूट कारक γ का चयन समय सीमा T के ज्ञान पर निर्भर करता है
  4. प्रयोगात्मक सीमा: प्रयोग मुख्य रूप से अपेक्षाकृत सरल वातावरण में किए गए हैं

भविष्य की दिशाएं

  1. पूर्व ज्ञान रहित सेटिंग: ऐसी स्व-अनुकूली विधियों का अन्वेषण करें जिन्हें T के पूर्व ज्ञान की आवश्यकता न हो
  2. अधिक जटिल वातावरण: बड़े पैमाने और अधिक जटिल वातावरण में विधि को सत्यापित करें
  3. सैद्धांतिक सुधार: कमजोर जुड़ाव जैसी मान्यताओं को शिथिल करें
  4. व्यावहारिक अनुप्रयोग: वास्तविक अनुप्रयोग परिदृश्यों में एल्गोरिदम प्रदर्शन का परीक्षण करें

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक कठोरता: पूर्ण सैद्धांतिक विश्लेषण और प्रमाण प्रदान करता है, निरंतर वातावरण PSRL के सैद्धांतिक अंतराल को भरता है
  2. एल्गोरिदम सरलता: मौजूदा विधियों की तुलना में, पुनः नमूनाकरण तंत्र अत्यंत सरल है, कार्यान्वयन और समझने में आसान है
  3. स्केलेबिलिटी: स्वाभाविक रूप से फ़ंक्शन सन्निकटन और उच्च-आयामी स्थिति स्थान का समर्थन करता है, बहुत व्यावहारिक मूल्य है
  4. नवीन दृष्टिकोण: छूट कारक को एल्गोरिदम डिजाइन उपकरण के रूप में पुनर्व्याख्यायित करता है, सैद्धांतिक अंतर्दृष्टि प्रदान करता है

कमजोरियां

  1. अपर्याप्त प्रयोगात्मक गहराई: प्रयोग मुख्य रूप से सरल वातावरण में किए गए हैं, बड़े पैमाने पर जटिल वातावरण के सत्यापन की कमी है
  2. पैरामीटर संवेदनशीलता: छूट कारक γ के चयन पर समस्या पैरामीटर पर निर्भरता, व्यावहारिक अनुप्रयोग में सावधानीपूर्वक ट्यूनिंग की आवश्यकता हो सकती है
  3. अपूर्ण तुलना: कुछ संबंधित अन्वेषण विधियों (जैसे UCB-प्रकार विधियों) के साथ तुलना की कमी है
  4. व्यावहारिक अनुप्रयोग केस की कमी: मुख्य रूप से सिद्धांत और सरल सिमुलेशन, वास्तविक अनुप्रयोग परिदृश्यों के सत्यापन की कमी है

प्रभाव

  1. सैद्धांतिक योगदान: निरंतर वातावरण अन्वेषण समस्या के लिए नया सैद्धांतिक ढांचा प्रदान करता है
  2. व्यावहारिक मूल्य: एल्गोरिदम की सरलता इसे अपनाने और विस्तारित करने में आसान बनाती है
  3. प्रेरणा महत्व: छूट कारक की नई व्याख्या भविष्य के एल्गोरिदम डिजाइन को प्रभावित कर सकती है
  4. पुनरुत्पादनीयता: एल्गोरिदम विवरण स्पष्ट है, सैद्धांतिक विश्लेषण पूर्ण है, अच्छी पुनरुत्पादनीयता है

लागू परिदृश्य

  1. निरंतर सुदृढ़ीकरण सीखना: लंबी अवधि की बातचीत की आवश्यकता वाले वातावरण जहां कोई प्राकृतिक एपिसोड संरचना नहीं है
  2. उच्च-आयामी स्थिति स्थान: जटिल वातावरण जहां पारंपरिक गणना-आधारित विधियां लागू नहीं होती हैं
  3. ऑनलाइन सीखना: ऐसे परिदृश्य जहां बातचीत के दौरान निरंतर सीखना और अनुकूलन आवश्यक है
  4. गहरे सुदृढ़ीकरण सीखना: मौजूदा गहरे RL ढांचे में एकीकृत किया जा सकता है

संदर्भ

पेपर सुदृढ़ीकरण सीखने के क्षेत्र के महत्वपूर्ण कार्यों का हवाला देता है, जिसमें शामिल हैं:

  • थॉम्पसन नमूनाकरण का शास्त्रीय कार्य (Thompson, 1933)
  • PSRL का अग्रणी कार्य (Osband et al., 2013)
  • निरंतर वातावरण से संबंधित अनुसंधान (Ouyang et al., 2017; Theocharous et al., 2018)
  • गहरे सुदृढ़ीकरण सीखने की महत्वपूर्ण प्रगति (Mnih et al., 2015)

समग्र मूल्यांकन: यह निरंतर वातावरण के पश्च नमूनाकरण विधि पर एक उच्च-गुणवत्ता वाला सैद्धांतिक सुदृढ़ीकरण सीखने का पेपर है जो महत्वपूर्ण योगदान देता है। एल्गोरिदम डिजाइन सरल और सुरुचिपूर्ण है, सैद्धांतिक विश्लेषण कठोर और पूर्ण है, इस क्षेत्र को नया दृष्टिकोण और उपकरण प्रदान करता है। हालांकि प्रयोगात्मक सत्यापन में सुधार की गुंजाइश है, लेकिन इसका सैद्धांतिक मूल्य और व्यावहारिक संभावना दोनों बहुत अच्छी हैं।