論文の概要: Oracle-Efficient Regret Minimization in Factored MDPs with Unknown
Structure
- arxiv url: http://arxiv.org/abs/2009.05986v4
- Date: Mon, 11 Oct 2021 12:23:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 02:40:38.031002
- Title: Oracle-Efficient Regret Minimization in Factored MDPs with Unknown
Structure
- Title(参考訳): Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
- Authors: Aviv Rosenberg and Yishay Mansour
- Abstract要約: 非絶対因子化マルコフ決定過程(FMDP)における後悔の研究
既存の全てのアルゴリズムは、FMDPの因子構造が学習者に事前に知られていると強く仮定する。
後悔を最小限に抑えながらFMDPの構造を学習する最初のアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 57.90236104782219
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study regret minimization in non-episodic factored Markov decision
processes (FMDPs), where all existing algorithms make the strong assumption
that the factored structure of the FMDP is known to the learner in advance. In
this paper, we provide the first algorithm that learns the structure of the
FMDP while minimizing the regret. Our algorithm is based on the optimism in
face of uncertainty principle, combined with a simple statistical method for
structure learning, and can be implemented efficiently given oracle-access to
an FMDP planner. Moreover, we give a variant of our algorithm that remains
efficient even when the oracle is limited to non-factored actions, which is the
case with almost all existing approximate planners. Finally, we leverage our
techniques to prove a novel lower bound for the known structure case, closing
the gap to the regret bound of Chen et al. [2021].
- Abstract(参考訳): 我々は,FMDPの因子構造が予め学習者に知られているという仮定を,既存の全てのアルゴリズムが強く仮定するFMDP (Non-episodic factored Markov decision process) における後悔の最小化について検討する。
本稿では,後悔を最小限に抑えながらfmdpの構造を学習する最初のアルゴリズムを提案する。
本アルゴリズムは,不確実性原理と構造学習のための単純な統計的手法を組み合わせた最適化手法に基づいており,fmdpプランナーへのoracleアクセスにより効率的に実装できる。
さらに,本アルゴリズムの変種として,ほとんどすべての既存の近似プランナーの場合のように,オラクルが非リファクタリング動作に限定されている場合でも,効率がよいアルゴリズムを提案する。
最後に、我々の手法を利用して、既知の構造の場合の新たな下限を証明し、Chenらによる後悔の限界とのギャップを埋める。
[2021].
関連論文リスト
- On Sequential Fault-Intolerant Process Planning [60.66853798340345]
我々は、逐次的フォールトトレラントプロセス計画(SFIPP)と呼ばれる計画問題を提案し、研究する。
SFIPPは、全ての段階が成功する場合にのみ計画が成功すると判断される多くの連続した多段階決定問題に共通する報酬構造をキャプチャする。
私たちは、異なるアクションを選択して、それぞれのステージで成功の確率を未知にする必要がある設定のために、確実に厳密なオンラインアルゴリズムを設計します。
論文 参考訳(メタデータ) (2025-02-07T15:20:35Z) - Alternating minimization for square root principal component pursuit [2.449191760736501]
平方根主成分探索(SRPCP)問題を解くための効率的なアルゴリズムを開発した。
具体的には、各反復が閉形式最適解を楽しむサブプロブレムを含む、チューニング不要な交互最小化(AltMin)アルゴリズムを提案する。
我々は,AltMin法をさらに加速するために,核ノルムの変分定式化とブラー・モンティロ分解に基づく手法を導入する。
論文 参考訳(メタデータ) (2024-12-31T14:43:50Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳(メタデータ) (2023-07-08T15:41:48Z) - Non-stationary Reinforcement Learning under General Function
Approximation [60.430936031067006]
まず,非定常MDPに対する動的ベルマンエルダー次元(DBE)と呼ばれる新しい複雑性指標を提案する。
提案する複雑性指標に基づいて,SW-OPEAと呼ばれる新しい信頼度セットに基づくモデルフリーアルゴリズムを提案する。
SW-OPEAは,変動予算がそれほど大きくない限り,有効に有効であることを示す。
論文 参考訳(メタデータ) (2023-06-01T16:19:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Towards Minimax Optimal Reinforcement Learning in Factored Markov
Decision Processes [53.72166325215299]
エピソード因子化マルコフ決定過程(FMDP)における最小強化学習について検討する。
第一に、分解された構造のリッチなクラスに対する最小限の後悔の保証を達成する。
2つ目は、少し悪い後悔をしながら、より良い計算複雑性を楽しみます。
論文 参考訳(メタデータ) (2020-06-24T00:50:17Z) - Deep unfolding of the weighted MMSE beamforming algorithm [9.518010235273783]
MISOダウンリンクチャネルに対するWMMSEアルゴリズムに対する深部展開の新たな適用法を提案する。
深層展開は、自然に専門家の知識を取り入れており、即時かつしっかりとしたアーキテクチャ選択の利点、トレーニング可能なパラメータの少ないこと、説明可能性の向上がある。
シミュレーションにより、ほとんどの設定において、展開されたWMMSEは、一定回数の反復に対して、WMMSEよりも優れているか、等しく動作することを示す。
論文 参考訳(メタデータ) (2020-06-15T14:51:20Z) - Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and
Tighter Regret Bounds for the Non-Episodic Setting [24.90164851620799]
非等化因子マルコフ決定過程(FMDP)における強化学習の研究
FMDPに対する2つの近似およびオラクル効率アルゴリズムを提案する。
我々のオラクル効率のアルゴリズムは、コンピュータネットワーク管理シミュレーションにおいて、これまで提案されていた近似アルゴリズムよりも優れていた。
論文 参考訳(メタデータ) (2020-02-06T15:19:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。