論文の概要: Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees

• arxiv url: http://arxiv.org/abs/2209.14414v1
• Date: Wed, 28 Sep 2022 20:49:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 16:28:19.087321
• Title: Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
• Title（参考訳）: 少数のサンプルとタイト保証者による強化学習のための最適後部サンプリング
• Authors: Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, Pierre Menard
• Abstract要約: 強化学習(OPSRL)のための楽観的後部サンプリングアルゴリズムを提案する。 殆どの$widetildemathcalO(sqrtH3SAT)$ ignoring $textpolylog(HSAT)$ termsにおいて、高い確率で再帰的な順序境界を保証する。 我々の境界は位数$Omega(sqrtH3SAT)$の下位境界と一致し、Agrawal と Jia が提起した開問題に答える。
• 参考スコア（独自算出の注目度）: 43.13918072870693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider reinforcement learning in an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon $H$ with $S$ states, and $A$ actions. The performance of an agent is measured by the regret after interacting with the environment for $T$ episodes. We propose an optimistic posterior sampling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs a number of posterior samples logarithmic in $H$, $S$, $A$, and $T$ per state-action pair. For OPSRL we guarantee a high-probability regret bound of order at most $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ ignoring $\text{poly}\log(HSAT)$ terms. The key novel technical ingredient is a new sharp anti-concentration inequality for linear forms which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges [1984] to Dirichlet distributions. Our bound matches the lower bound of order $\Omega(\sqrt{H^3SAT})$, thereby answering the open problems raised by Agrawal and Jia [2017b] for the episodic setting.
• Abstract（参考訳）: 我々は,horizon$h$と$s$状態,および$a$アクションのエピソディック,有限、ステージ依存のマルコフ決定過程によってモデル化された環境における強化学習を考える。 エージェントのパフォーマンスは、T$エピソードの環境と対話した後の後悔によって測定される。 本稿では, 補助学習のための楽観的後部サンプリングアルゴリズム(OPSRL)を提案する。これは単純な後部サンプリングの変種であり, 後部サンプルの対数値が$H$, $S$, $A$, $T$でのみ必要である。 OPSRL では、高確率のリフレッシュバウンダリを $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ ignoring $\text{poly}\log(HSAT)$ terms で保証する。 重要な新しい技術的要素は、独立興味を持つかもしれない線型形式に対する新しい鋭い反集中不等式である。 具体的には、alfers と dinges [1984] によるベータ分布の正規近似に基づく下限をディリクレ分布に拡張する。 我々の境界は位数 $\Omega(\sqrt{H^3SAT})$ の下界と一致するので、エピソード的設定に対して Agrawal と Jia [2017b] が提起した開問題に答える。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning [29.44582058149344]
  n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。 次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
  論文  参考訳（メタデータ） (2023-02-09T14:20:14Z)
• Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds [24.571530193140916]
  エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。 モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。 いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
  論文  参考訳（メタデータ） (2022-10-25T14:30:48Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)

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

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