論文の概要: Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes
with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2205.13451v1
- Date: Thu, 26 May 2022 15:55:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-27 12:39:00.981815
- Title: Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes
with Bandit Feedback
- Title(参考訳): 帯域フィードバックによる逆マルコフ決定過程の追従型リード
- Authors: Yan Dai, Haipeng Luo and Liyu Chen
- Abstract要約: 本稿では, 損失関数が時間とともに変化し, 逆選択されるAMDP(Adversarial Markov Decision Processs)に対する後悔について考察する。
Online-Mirror-Descent(OMD)法によるこの問題の研究が急増しているが、Follow-the-Perturbed-Leader(FTPL)法についてはほとんど知られていない。
我々は,帯域幅のフィードバックと遷移を伴う無限水平環境において,AMDPを学習するための最初のノンレグレットアルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 35.687473978249535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider regret minimization for Adversarial Markov Decision Processes
(AMDPs), where the loss functions are changing over time and adversarially
chosen, and the learner only observes the losses for the visited state-action
pairs (i.e., bandit feedback). While there has been a surge of studies on this
problem using Online-Mirror-Descent (OMD) methods, very little is known about
the Follow-the-Perturbed-Leader (FTPL) methods, which are usually
computationally more efficient and also easier to implement since it only
requires solving an offline planning problem. Motivated by this, we take a
closer look at FTPL for learning AMDPs, starting from the standard episodic
finite-horizon setting. We find some unique and intriguing difficulties in the
analysis and propose a workaround to eventually show that FTPL is also able to
achieve near-optimal regret bounds in this case. More importantly, we then find
two significant applications: First, the analysis of FTPL turns out to be
readily generalizable to delayed bandit feedback with order-optimal regret,
while OMD methods exhibit extra difficulties (Jin et al., 2022). Second, using
FTPL, we also develop the first no-regret algorithm for learning communicating
AMDPs in the infinite-horizon setting with bandit feedback and stochastic
transitions. Our algorithm is efficient assuming access to an offline planning
oracle, while even for the easier full-information setting, the only existing
algorithm (Chandrasekaran and Tewari, 2021) is computationally inefficient.
- Abstract(参考訳): 我々は、時間とともに損失関数が変化し、逆選択され、学習者は訪問した状態-行動ペア(すなわちバンディットフィードバック)の損失のみを観察する敵マルコフ決定プロセス(amdps)に対する後悔の最小化を検討する。
Online-Mirror-Descent (OMD) 法によるこの問題の研究が急増しているが、オフライン計画問題の解決のみを必要とするため、計算効率が良く実装が容易なFollow-the-Perturbed-Leader (FTPL) 手法についてはほとんど知られていない。
これに触発された我々は、標準のエピソード有限ホライゾン設定から始めて、AMDPを学習するためのFTPLについてより詳しく検討する。
分析の難しさはいくつか見出され,最終的にFTPLがほぼ最適の後悔境界を達成できることを示すための回避策が提案されている。
さらに重要なのは、2つの重要な応用が見つかることだ: まず、FTPLの分析は、順序-最適の後悔を伴う遅延帯域フィードバックに対して容易に一般化可能であること、OMD法は余計な困難を示す(Jin et al., 2022)。
第2に、FTPLを用いて、帯域幅フィードバックと確率遷移を伴う無限水平環境におけるAMDP間の通信を学習するための最初のノンレグレットアルゴリズムを開発する。
我々のアルゴリズムはオフラインの計画オラクルへのアクセスを効率的に仮定する一方、より簡単な情報設定であっても、既存のアルゴリズム(Chandrasekaran, Tewari, 2021)は計算的に非効率である。
関連論文リスト
- Truly No-Regret Learning in Constrained MDPs [66.28706907897285]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳(メタデータ) (2024-02-24T09:47:46Z) - No-Regret Reinforcement Learning in Smooth MDPs [24.249446550171307]
本稿では,これまで提案されてきたほとんどの設定を一般化した,決定プロセス(MDP)に関する新たな構造仮定を提案する。
本稿では,2つのアルゴリズムを用いて,$nu-$smoothnessにおける後悔の最小化を提案する。
結果とRL理論の最先端技術を比較し,アルゴリズムが最高の保証を達成することを示す。
論文 参考訳(メタデータ) (2024-02-06T08:18:14Z) - Learning to Control under Time-Varying Environment [18.48729114775298]
本稿では,線形時間変化(LTV)力学系における後悔の問題について検討する。
提案するオンラインアルゴリズムは, 計算に難易度を保証した最初のオンラインアルゴリズムである。
論文 参考訳(メタデータ) (2022-06-06T11:40:46Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳(メタデータ) (2021-11-24T07:14:57Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳(メタデータ) (2021-01-31T16:49:07Z) - Regret minimization in stochastic non-convex learning via a
proximal-gradient approach [80.59047515124198]
機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。
我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
論文 参考訳(メタデータ) (2020-10-13T09:22:21Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Refined Analysis of FPL for Adversarial Markov Decision Processes [9.188318506016897]
FPL(Follow-the-PerturbedLeader)ベースのアルゴリズムは、以前の文献で提案されている。
我々は、FPLベースのアルゴリズムを両方の設定で解析し、より高速でより単純なアルゴリズムを用いて、現在の最良後悔境界をマッチングする。
論文 参考訳(メタデータ) (2020-08-21T01:12:10Z) - More Practical and Adaptive Algorithms for Online Quantum State Learning [11.836183463815653]
本稿では,量子状態のオンライン学習を促進するアルゴリズムを開発する。
まず,Tallis-2エントロピーを用いた正規化Follow-the-Leader (RFTL) 法により,完全な後方視でO(sqrtMT)$の総損失が得られることを示す。
次に,古典的な調整学習率スケジュールに基づくパラメータフリーアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-01T15:17:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。