論文の概要: From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses
- arxiv url: http://arxiv.org/abs/2205.07704v1
- Date: Mon, 16 May 2022 14:13:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 19:10:47.540049
- Title: From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses
- Title（参考訳）: DirichletからRubinへ - ボーナスのないRLでの最適探索
- Authors: Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey
Samsonov, Yunhao Tang, Michal Valko, Pierre Menard
- Abstract要約: Bayes-UCBVI は Kaufmann らによる Bayes-UCB アルゴリズムの自然な拡張である。
私たちは、$widetildeO(sqrtH3SAT)$ ここで、$H$はひとつのエピソードの長さ、$S$は状態の数、$A$はアクションの数、$T$はエピソードの数で、$Omega(sqrtH3SAT)$の低いバウンドの$Omega(sqrtH3SAT)$と一致する。
- 参考スコア（独自算出の注目度）: 47.6564858125342
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular,
stage-dependent, episodic Markov decision process: a natural extension of the
Bayes-UCB algorithm by Kaufmann et al. (2012) for multi-armed bandits. Our
method uses the quantile of a Q-value function posterior as upper confidence
bound on the optimal Q-value function. For Bayes-UCBVI, we prove a regret bound
of order $\widetilde{O}(\sqrt{H^3SAT})$ where $H$ is the length of one episode,
$S$ is the number of states, $A$ the number of actions, $T$ the number of
episodes, that matches the lower-bound of $\Omega(\sqrt{H^3SAT})$ up to
poly-$\log$ terms in $H,S,A,T$ for a large enough $T$. To the best of our
knowledge, this is the first algorithm that obtains an optimal dependence on
the horizon $H$ (and $S$) without the need for an involved Bernstein-like bonus
or noise. Crucial to our analysis is a new fine-grained anti-concentration
bound for a weighted Dirichlet sum that can be of independent interest. We then
explain how Bayes-UCBVI can be easily extended beyond the tabular setting,
exhibiting a strong link between our algorithm and Bayesian bootstrap (Rubin,
1981).
- Abstract（参考訳）: 我々は,多腕包帯に対するBayes-UCBアルゴリズムの自然な拡張として,表層・ステージ依存・エピソードマルコフ決定過程における強化学習のためのBayes-UCBVIアルゴリズムを提案する。
提案手法では,Q値関数の後続の量子化を,最適Q値関数の上限値として用いる。
Bayes-UCBVI の場合、$\widetilde{O}(\sqrt{H^3SAT})$ ここで$H$はひとつのエピソードの長さ、$S$は状態の数、$A$はアクションの数、$T$は$\Omega(\sqrt{H^3SAT})$の低いバウンドの$\Omega(\sqrt{H^3SAT})$と一致する$H,S,A,T$は十分大きな$T$である。
我々の知る限りでは、このアルゴリズムはバーンスタインのようなボーナスやノイズを必要とせずに、horizon $h$(および$s$)の最適依存を得る最初のアルゴリズムである。
我々の分析に不可欠なのは、独立利害関係を持つ重み付きディリクレ和に対する新しい細粒度の反集中結合である。
次に、ベイズ-UCBVI が表の設定を超えて容易に拡張可能であることを説明し、我々のアルゴリズムとベイズブートストラップの強い関係を示す(Rubin, 1981)。
関連論文リスト
- Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Optimistic Posterior Sampling for Reinforcement Learning with Few
Samples and Tight Guarantees [43.13918072870693]
強化学習(OPSRL)のための楽観的後部サンプリングアルゴリズムを提案する。
殆どの$widetildemathcalO(sqrtH3SAT)$ ignoring $textpolylog(HSAT)$ termsにおいて、高い確率で再帰的な順序境界を保証する。
我々の境界は位数$Omega(sqrtH3SAT)$の下位境界と一致し、Agrawal と Jia が提起した開問題に答える。
論文 参考訳（メタデータ） (2022-09-28T20:49:34Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
論文 参考訳（メタデータ） (2021-02-19T01:42:50Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。
さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
論文 参考訳（メタデータ） (2020-10-01T17:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。