論文の概要: Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection
- arxiv url: http://arxiv.org/abs/2110.14798v1
- Date: Wed, 27 Oct 2021 22:07:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-29 15:41:37.074585
- Title: Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection
- Title(参考訳): 線形mdpにおける強化学習 : 後悔と表現の選択
- Authors: Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli,
Alessandro Lazaric and Matteo Pirotta
- Abstract要約: 線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
- 参考スコア(独自算出の注目度): 136.4014229319618
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the role of the representation of state-action value functions in
regret minimization in finite-horizon Markov Decision Processes (MDPs) with
linear structure. We first derive a necessary condition on the representation,
called universally spanning optimal features (UNISOFT), to achieve constant
regret in any MDP with linear reward function. This result encompasses the
well-known settings of low-rank MDPs and, more generally, zero inherent Bellman
error (also known as the Bellman closure assumption). We then demonstrate that
this condition is also sufficient for these classes of problems by deriving a
constant regret bound for two optimistic algorithms (LSVI-UCB and ELEANOR).
Finally, we propose an algorithm for representation selection and we prove that
it achieves constant regret when one of the given representations, or a
suitable combination of them, satisfies the UNISOFT condition.
- Abstract(参考訳): 線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
この結果は、低ランク MDP のよく知られた設定や、より一般的にはゼロ固有ベルマン誤差(ベルマン閉包仮定とも呼ばれる)を含む。
次に、この条件は、2つの楽観的アルゴリズム(LSVI-UCB と ELEANOR )に対して一定の後悔を導出することで、これらの問題のクラスに十分であることを示す。
最後に, 表現選択のためのアルゴリズムを提案し, 与えられた表現の1つ, あるいは適切な組み合わせがUNISOFT条件を満たす場合, 常に後悔することを示す。
関連論文リスト
- Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳(メタデータ) (2022-11-03T16:42:40Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
一次元回帰問題に対する連続領域定式化を提案する。
リプシッツ定数をユーザ定義上界を用いて明示的に制御する。
いずれの問題も、連続的かつ断片的線形なグローバル最小化を許容していることが示される。
論文 参考訳(メタデータ) (2021-12-27T07:03:43Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳(メタデータ) (2021-06-24T13:46:09Z) - Nonstationary Reinforcement Learning with Linear Function Approximation [24.910327525332463]
ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。
我々はまず、$textttLSVI-UCB-Restart$アルゴリズムを開発し、変動予算が分かっている場合にその動的後悔境界を確立する。
次にパラメータフリーアルゴリズムである$textttAda-LSVI-UCB-Restart$を提案する。
論文 参考訳(メタデータ) (2020-10-08T20:07:44Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。