論文の概要: Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
- arxiv url: http://arxiv.org/abs/2611.17214v1
- Date: Thu, 12 Nov 2026 18:10:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.582266
- Title: Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal $\sqrt S$ and $\sqrt K$ Dependencies in Tabular and Linear AMDPs
- Title(参考訳): 非遅延逆MDPへのフィードバック遅延の導入: Optimal $\sqrt S$および$\sqrt K$ Dependencies in Tabular and Linear AMDPs
- Abstract要約: 先天的なマルコフ決定過程 (AMDP) において, 未知の遷移と包括的フィードバックによる後悔について検討した。
提案手法は,フィードバック遅延と呼ばれる手法で,フィードバックが遅れたかのようにポリシーを更新しながら,今後のエピソードを用いてポリシーのQ-関数を推定する。
- 参考スコア(独自算出の注目度): 4.822293643930893
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with $S$ states, $A$ actions, and horizon $H$, the best known $K$-episode regret is $\tilde O(HS\sqrt{AK})$, whose $\sqrt S$ gap to the $Ω(H\sqrt{SAK})$ lower bound has long remained open. In linear AMDPs with $d$-dimensional features, after a five-year line of improvements starting from $K^{14/15}$, computationally efficient algorithms without a simulator or exploratory assumptions still only attain $\tilde O(K^{3/4})$ regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on $K$. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, $\tilde O(\text{poly}(H)\sqrt{SAK})$ regret in tabular AMDPs, resolving the open problem; and $\tilde O(\text{poly}(d,H)\sqrt K)$ regret in linear AMDPs, giving the first efficient algorithm optimal in $K$. They also naturally extend to delayed AMDPs with a total feedback delay $\mathfrak D$, yielding the first bounds optimal in $S$ and $\mathfrak D$ (tabular) and in $K$ and $\mathfrak D$ (linear).
- Abstract(参考訳): 本研究は,表在性マルコフ決定過程(AMDP)において,未知の遷移と包括的フィードバックによる後悔の最小化について検討する。
S$状態、$A$アクション、および平らな$H$を持つ表式AMDPにおいて、最もよく知られている$K$-エピソード後悔は$\tilde O(HS\sqrt{AK})$であり、$\sqrt S$ の $Ω(H\sqrt{SAK})$ とのギャップは長い間開いていない。
$d$-dimensional特徴を持つ線形AMDPでは、$K^{14/15}$から5年間の改良を経て、シミュレータや探索的仮定のない計算効率の良いアルゴリズムは、まだ$\tilde O(K^{3/4})$ にしか達していない。
過去のデータは、現在のものとは異なる(そして相関している)以前のポリシーに由来するが、将来のエピソードのポリシーを凍結すると、$K$への依存が悪化する。
そこで我々は,フィードバック遅延と呼ばれる一般的な手法を提案し,フィードバックが遅れたかのように,今後のエピソードを用いてポリシーのQ-関数を推定する。
フィードバックの遅延は通常、環境によって課される障害であるが、ここでは自発的に導入され、驚くべきことに、余分なコストがかからない。
我々は、遅延中の政策変化を考慮に入れた幾何学的リサンプリング(Geometric Resampling with Rejection, GRR)を開発し、来訪者がほとんど来訪しない状態-行動ペアの長時間の遅延を避けるための来訪確率をしきい値とした。
この統一手法により、当社のポリシー最適化アルゴリズムは、高い確率で、表式AMDPにおける後悔$$\tilde O(\text{poly}(H)\sqrt{SAK})、開問題の解決$$\tilde O(\text{poly}(d,H)\sqrt K)$後悔$線形AMDPにおける後悔$$$\tilde O(\text{poly}(d,H)\sqrt K)を達成し、最初の効率的なアルゴリズムを$K$で最適にする。
また、完全なフィードバック遅延を$\mathfrak D$と$\mathfrak D$(タブラル)と$K$と$\mathfrak D$(リニア)で最適となるような遅延AMDPまで自然に拡張する。
関連論文リスト
- Strongly Adaptive Online Learning with Time-Varying Movement Costs [18.95079821752574]
我々は,OCO(Online Convex Optimization)に対する時間変動移動コストの強い適応的後悔について検討した。
このフレームワークは、環境と切り替え決定のコストが時間とともに変動する複雑なシーケンシャルな意思決定問題を捉えます。
遅れたフィードバックの下で、最初に強く適応的な保証を確立する。
論文 参考訳(メタデータ) (2026-10-23T14:54:13Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳(メタデータ) (2026-07-22T07:42:19Z) - A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。
バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
論文 参考訳(メタデータ) (2026-02-02T18:17:34Z) - Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。
PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。
我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
論文 参考訳(メタデータ) (2025-07-15T20:19:32Z) - Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳(メタデータ) (2025-02-06T12:03:24Z) - Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳(メタデータ) (2023-05-20T07:54:07Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳(メタデータ) (2021-09-29T14:07:21Z) - Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。
本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-29T16:47:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。