論文の概要: A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
- arxiv url: http://arxiv.org/abs/2106.13013v1
- Date: Thu, 24 Jun 2021 13:46:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-25 15:01:07.765162
- Title: A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
- Title（参考訳）: 有限ホリゾンmdpに対する完全問題依存的後悔下限
- Authors: Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric
- Abstract要約: 有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 117.82903457289584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We derive a novel asymptotic problem-dependent lower-bound for regret
minimization in finite-horizon tabular Markov Decision Processes (MDPs). While,
similar to prior work (e.g., for ergodic MDPs), the lower-bound is the solution
to an optimization problem, our derivation reveals the need for an additional
constraint on the visitation distribution over state-action pairs that
explicitly accounts for the dynamics of the MDP. We provide a characterization
of our lower-bound through a series of examples illustrating how different MDPs
may have significantly different complexity. 1) We first consider a "difficult"
MDP instance, where the novel constraint based on the dynamics leads to a
larger lower-bound (i.e., a larger regret) compared to the classical analysis.
2) We then show that our lower-bound recovers results previously derived for
specific MDP instances. 3) Finally, we show that, in certain "simple" MDPs, the
lower bound is considerably smaller than in the general case and it does not
scale with the minimum action gap at all. We show that this last result is
attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a
regret upper-bound based on policy gaps for an optimistic algorithm.
- Abstract（参考訳）: 有限水平タブ状マルコフ決定過程 (MDPs) において, 後悔最小化のための新しい漸近的問題依存下界を導出する。
従来の作業(例えばエルゴード型MDP)と同様に、低いバウンドは最適化問題の解であるが、我々の導出は、MDPの力学を明示的に説明する状態-作用対上の訪問分布にさらなる制約を加える必要があることを明らかにする。
我々は、mdpの異なる複雑さがいかに大きく異なるかを示す一連の例を通して、低いバウンドの特性を提供する。
1) まず「難解」な MDP のインスタンスを考える。そこでは,力学に基づく新しい制約が,古典的解析に比べて大きな下界(すなわち,大きな後悔)をもたらす。
2) この結果から, 特定のMDPインスタンスに先立って得られた結果が得られた。
3) 最後に、ある「単純な」mdpでは、下限は一般的な場合よりもかなり小さく、最小の動作ギャップではスケールしないことを示す。
この最後の結果(最大$poly(h)$項、ただし$h$は地平線)は、楽観的アルゴリズムのポリシーギャップに基づく後悔の上限を提供することによって達成可能であることを示す。
関連論文リスト
- Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
論文 参考訳（メタデータ） (2022-06-13T15:58:14Z) - Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。
私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。
彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
論文 参考訳（メタデータ） (2022-03-17T11:19:41Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討
LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。
鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
論文 参考訳（メタデータ） (2021-02-09T16:49:58Z) - Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds
Revisited [46.682733513730334]
エピソードMDPにおける標本の複雑さと後悔に対する問題非依存の新たな下位境界を提案する。
我々の主な貢献は、非定常MDPにおける最良のポリシー識別のための$(varepsilon,delta)$-PACアルゴリズムのサンプル複雑性に基づいて、$Omega((H3SA/epsilon2)log (1/delta))$の新たな低い境界である。
論文 参考訳（メタデータ） (2020-10-07T17:23:01Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。