論文の概要: Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?

• arxiv url: http://arxiv.org/abs/2106.08771v1
• Date: Wed, 16 Jun 2021 13:29:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-17 17:41:25.350215
• Title: Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?
• Title（参考訳）: マルコフバンドの強化学習:後方サンプリングは楽観主義よりもスケーラブルか?
• Authors: Nicolas Gast (POLARIS), Bruno Gaujal (POLARIS), Kimang Khun (POLARIS)
• Abstract要約: 古典マルコフ帯域問題に対する学習アルゴリズムを割引で検討する。 本稿では, PSRL [24] と UCRL2 [2] を適用し, 問題構造を利用する方法について説明する。 MB-PSRL と MB-UCRL2 のエピソード的後悔は、K がエピソード数、n が盗賊数、S が各盗賊の状態数である(S $sqrt$nK)ことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study learning algorithms for the classical Markovian bandit problem with discount. We explain how to adapt PSRL [24] and UCRL2 [2] to exploit the problem structure. These variants are called MB-PSRL and MB-UCRL2. While the regret bound and runtime of vanilla implementations of PSRL and UCRL2 are exponential in the number of bandits, we show that the episodic regret of MB-PSRL and MB-UCRL2 isÕ(S $\sqrt$ nK) where K is the number of episodes, n is the number of bandits and S is the number of states of each bandit (the exact bound in S, n and K is given in the paper). Up to a factor $\sqrt$ S, this matches the lower bound of $\Omega$($\sqrt$ SnK) that we also derive in the paper. MB-PSRL is also computationally efficient: its runtime is linear in the number of bandits. We further show that this linear runtime cannot be achieved by adapting classical non-Bayesian algorithms such as UCRL2 or UCBVI to Markovian bandit problems. Finally, we perform numerical experiments that confirm that MB-PSRL outperforms other existing algorithms in practice, both in terms of regret and of computation time.
• Abstract（参考訳）: 古典マルコフ帯域問題に対する学習アルゴリズムを割引で検討する。 本稿では, PSRL [24] と UCRL2 [2] を適用し, 問題構造を利用する方法について説明する。 これらの変種はMB-PSRLとMB-UCRL2と呼ばれる。 PSRL と UCRL2 のバニラ実装の後悔と実行は、バンドイット数で指数関数的であるが、MB-PSRL と MB-UCRL2 のエピソディックな後悔は、K がエピソード数、n がバンドイット数、S が各バンドイットの状態数である(S, n と K の正確な境界は、論文の中で与えられる)。 最大で$\sqrt$ s とすると、これは論文で導かれる$\omega$($\sqrt$ snk) の下限に一致する。 MB-PSRLも計算効率が良く、その実行時間は帯域数で線形である。 さらに、この線形ランタイムは、UCRL2やUCBVIのような古典的非ベイズ的アルゴリズムをマルコフ的帯域問題に適応させることによって達成できないことを示す。 最後に, mb-psrlが後悔時間と計算時間の両方において, 既存のアルゴリズムよりも優れていることを確認する数値実験を行う。

関連論文リスト

• Binary Reward Labeling: Bridging Offline Preference and Reward-Based Reinforcement Learning [5.480108613013526]
  本稿では、報酬ベースのオフラインRLと優先ベースのオフラインRLのギャップを埋める一般的なフレームワークを提案する。 我々の重要な洞察は、好みフィードバックを2進報酬ラベリング(BRL)を通してスカラー報酬に変換することである。 我々は、標準D4RLベンチマークに基づいて、好みデータセットに基づいて、我々のフレームワークを実証的にテストする。
  論文  参考訳（メタデータ） (2024-06-14T23:40:42Z)
• More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning [58.626683114119906]
  本研究では,分散強化学習(DistRL)がオンラインとオフラインのRLの2次境界を得ることができることを示す。 我々の結果は、低ランク MDP とオフライン RL に対する最初の2階境界である。
  論文  参考訳（メタデータ） (2024-02-11T13:25:53Z)
• Is RLHF More Difficult than Standard RL? [31.972393805014903]
  ヒューマンフィードバック(RLHF)からの強化学習は優先信号から学習し、標準強化学習(RL)は報酬信号から直接学習する。 理論的には、幅広い選好モデルに対して、我々は、報酬に基づくRLのアルゴリズムと技法を直接的に解き、少ないか、余分なコストで解決できることを証明している。
  論文  参考訳（メタデータ） (2023-06-25T03:18:15Z)
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
  量子強化学習(RL)のための新しいUCRL型アルゴリズムを提案する。 我々は$mathcalO(mathrmpoly(S, A, H, log T))$ the worst-case regret for it, where $T$ is the number of episodes。 具体的には、$d$次元線形表現を持つ線形混合MDPに対する値目標回帰(VTR)に基づく量子アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-21T16:23:11Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Improved Exploration in Factored Average-Reward MDPs [23.096751699592133]
  我々は、未知の因子マルコフ決定過程(FMDP)における平均回帰基準の下での後悔の最小化タスクを考える。 我々は、遷移関数の個々の要素に対して定義されたバーンスタイン型信頼集合に依存する、DBN-UCRLと呼ばれる人気のあるUCRL2戦略にインスパイアされた、新しい後悔の最小化戦略を導入する。 本稿では,DBN-UCRL は,一般的な因子分解構造において,$mathcal S_i$'s の大きさとそれに関連する直径関連項の依存性から,既存の後悔境界よりも厳格に改善された後悔境界を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-09T21:15:01Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。