論文の概要: Logarithmic Regret of Exploration in Average Reward Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2502.06480v1
- Date: Mon, 10 Feb 2025 13:59:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:35:04.384836
- Title: Logarithmic Regret of Exploration in Average Reward Markov Decision Processes
- Title(参考訳): 平均逆マルコフ決定過程における探索の対数回帰
- Authors: Victor Boone, Bruno Gaujal,
- Abstract要約: 後悔のための最先端のアルゴリズムは、確立されたフレームワークに従う。
我々は、Doubleling Trick(DT)ルールをVanishing Multiplicative(VM)ルールに置き換える上で、大きな利点があることを示します。
- 参考スコア(独自算出の注目度): 2.9158689853305693
- License:
- Abstract: In average reward Markov decision processes, state-of-the-art algorithms for regret minimization follow a well-established framework: They are model-based, optimistic and episodic. First, they maintain a confidence region from which optimistic policies are computed using a well-known subroutine called Extended Value Iteration (EVI). Second, these policies are used over time windows called episodes, each ended by the Doubling Trick (DT) rule or a variant thereof. In this work, without modifying EVI, we show that there is a significant advantage in replacing (DT) by another simple rule, that we call the Vanishing Multiplicative (VM) rule. When managing episodes with (VM), the algorithm's regret is, both in theory and in practice, as good if not better than with (DT), while the one-shot behavior is greatly improved. More specifically, the management of bad episodes (when sub-optimal policies are being used) is much better under (VM) than (DT) by making the regret of exploration logarithmic rather than linear. These results are made possible by a new in-depth understanding of the contrasting behaviors of confidence regions during good and bad episodes.
- Abstract(参考訳): 平均的な報酬 Markov の決定プロセスでは、後悔の最小化のための最先端のアルゴリズムは、確立されたフレームワークに従っている。
まず、楽観的なポリシーが、拡張価値イテレーション(EVI)と呼ばれるよく知られたサブルーチンを使って計算される信頼領域を維持する。
第2に、これらのポリシーは、エピソードと呼ばれる時間的ウィンドウを通じて使用され、それぞれがDoubleling Trick(DT)ルールまたはその変種によって終了する。
本稿では、EVIを変更することなく、Vanishing Multiplicative (VM) ルールと呼ぶ別の単純なルールで(DT)を置き換えることに大きな利点があることを示します。
エピソードを(VM)で管理する場合、理論上も現実上も(DT)より優れているが、一方的な振る舞いは大幅に改善される。
より具体的には、悪いエピソード(サブ最適化ポリシーが使用されている場合)の管理は(DT)よりも(VM)の方がずっと優れている。
これらの結果は、良いエピソードと悪いエピソードにおける信頼領域の対照的な振る舞いの深い理解によって可能となる。
関連論文リスト
- Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。
本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
論文 参考訳(メタデータ) (2024-11-05T13:55:52Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳(メタデータ) (2023-02-18T19:46:11Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - Provable Benefits of Actor-Critic Methods for Offline Reinforcement
Learning [85.50033812217254]
アクター批判法はオフラインの強化学習に広く用いられているが、理論的にはそれほどよく理解されていない。
ペシミズムの原理を自然に取り入れた新しいオフラインアクター批判アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-08-19T17:27:29Z) - Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds
for Episodic Reinforcement Learning [50.44564503645015]
有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。
楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
論文 参考訳(メタデータ) (2021-07-02T20:36:05Z) - Variance Penalized On-Policy and Off-Policy Actor-Critic [60.06593931848165]
本稿では,平均値と変動値の両方を含むパフォーマンス基準を最適化する,オン・ポリティィおよびオフ・ポリティィ・アクター・クリティカルなアルゴリズムを提案する。
提案手法は, アクタ批判的かつ事前の分散-ペナライゼーションベースラインに匹敵するだけでなく, リターンのばらつきが低いトラジェクトリも生成する。
論文 参考訳(メタデータ) (2021-02-03T10:06:16Z) - Convergence Proof for Actor-Critic Methods Applied to PPO and RUDDER [6.9478331974594045]
我々は、よく知られたPPOと最近導入されたRUDDERの収束性を示す。
本研究は, エピソード標本を用いたアクター批判的手法に有効であり, 学習中により欲求的になる方針を持つ。
論文 参考訳(メタデータ) (2020-12-02T18:47:06Z) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳(メタデータ) (2020-10-24T11:02:45Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳(メタデータ) (2020-02-19T15:41:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。