論文の概要: 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)は計算的に非効率である。
関連論文リスト
- Regret-Free Reinforcement Learning for LTL Specifications [6.342676126028222]
強化学習は、未知のダイナミクスを持つシステムの最適制御ポリシーを学習するための有望な方法である。
現在のRLベースの手法は保証のみを提供しており、学習フェーズにおける過渡的なパフォーマンスについての洞察を与えていない。
マルコフ決定プロセス上の仕様の一般的なクラスに対処するコントローラを学習するための,最初の後悔のないオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-18T20:01:45Z) - Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。
本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-30T16:00:23Z) - Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。
プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。
予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
論文 参考訳（メタデータ） (2024-09-24T02:37:33Z) - Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。
インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。
多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
論文 参考訳（メタデータ） (2024-09-04T14:26:58Z) - Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知の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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。