論文の概要: Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits
- arxiv url: http://arxiv.org/abs/2502.04662v1
- Date: Fri, 07 Feb 2025 05:05:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:55:07.238578
- Title: Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits
- Title（参考訳）: マルコフデータを用いた逆回転型TD学習:有限時間率と基本限界
- Authors: Sreejeet Maity, Aritra Mitra,
- Abstract要約: 厳しい現実世界の環境に動機付けられ、敵の堅牢性の観点から政策評価問題を再考する。
我々はRobust-TDと呼ばれる新しいアルゴリズムを開発し、その有限時間保証がバニラTDの線形関数近似と小さな$O(epsilon)$項に一致することを証明した。
我々の知る限り、これらの結果はマルコフノイズによって駆動される敵近似スキームの文脈における最初のものである。
- 参考スコア（独自算出の注目度）: 2.07180164747172
- License:
- Abstract: One of the most basic problems in reinforcement learning (RL) is policy evaluation: estimating the long-term return, i.e., value function, corresponding to a given fixed policy. The celebrated Temporal Difference (TD) learning algorithm addresses this problem, and recent work has investigated finite-time convergence guarantees for this algorithm and variants thereof. However, these guarantees hinge on the reward observations being always generated from a well-behaved (e.g., sub-Gaussian) true reward distribution. Motivated by harsh, real-world environments where such an idealistic assumption may no longer hold, we revisit the policy evaluation problem from the perspective of adversarial robustness. In particular, we consider a Huber-contaminated reward model where an adversary can arbitrarily corrupt each reward sample with a small probability $\epsilon$. Under this observation model, we first show that the adversary can cause the vanilla TD algorithm to converge to any arbitrary value function. We then develop a novel algorithm called Robust-TD and prove that its finite-time guarantees match that of vanilla TD with linear function approximation up to a small $O(\epsilon)$ term that captures the effect of corruption. We complement this result with a minimax lower bound, revealing that such an additive corruption-induced term is unavoidable. To our knowledge, these results are the first of their kind in the context of adversarial robustness of stochastic approximation schemes driven by Markov noise. The key new technical tool that enables our results is an analysis of the Median-of-Means estimator with corrupted, time-correlated data that might be of independent interest to the literature on robust statistics.
- Abstract（参考訳）: 強化学習(RL)における最も基本的な問題の1つは政策評価である。
著名な時間差分法(TD)学習アルゴリズムはこの問題に対処し、近年の研究では、このアルゴリズムとその変種に対する有限時間収束保証について検討している。
しかし、これらの保証は、報奨観測が常に(例えば、ガウス以下の)真の報奨分布から生成されることを保証している。
このような理想主義的な仮定がもはや成り立たないような厳しい現実世界の環境に動機付けられ、敵の堅牢性の観点から政策評価問題を再考する。
特に、敵が任意の報酬サンプルを小さな確率$\epsilon$で任意に破壊できるハマー汚染報酬モデルを考える。
この観測モデルの下では、まず敵が任意の値関数にバニラTDアルゴリズムを収束させることができることを示す。
次に、Robust-TDと呼ばれる新しいアルゴリズムを開発し、その有限時間保証がバニラTDと線形関数近似に一致することを証明した。
この結果をミニマックス下限で補うと、そのような加法的汚職誘発項は避けられないことが分かる。
我々の知る限り、これらの結果はマルコフ雑音によって駆動される確率近似スキームの対角的堅牢性という文脈において最初のものである。
我々の結果を実現するための重要な新しい技術ツールは、堅牢な統計に関する文献に独立した関心を持つ可能性のある、腐敗した時間関連データを用いて、Median-of-Means推定器の分析である。
関連論文リスト
- Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。
マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
論文 参考訳（メタデータ） (2024-11-10T01:47:11Z) - Robust Q-Learning under Corrupted Rewards [2.07180164747172]
本稿では,Q-Learningアルゴリズムの強汚染攻撃モデルに対する堅牢性について検討する。
本研究では,実演的ベルマン演算子を構築するために,履歴報酬データを用いた新しい頑健な同期Q-ラーニングアルゴリズムを開発した。
我々の結果は、真の報酬分布が無限に支持されたとしても、有界な第2モーメントを許容するならば、維持され続ける。
論文 参考訳（メタデータ） (2024-09-05T04:37:02Z) - Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes [44.974100402600165]
意思決定プロセス(MDP)に対する最良パラメトリックかつ最悪の摂動の評価について検討する。
我々は、元のMDPからの遷移観測を用いて、それらが同一または異なるポリシーの下で生成されるかのどちらかを判断する。
我々の推定器はウォルドの信頼区間を用いた統計的推測も行う。
論文 参考訳（メタデータ） (2024-03-29T18:11:49Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳（メタデータ） (2021-10-21T15:25:15Z) - Risk Minimization from Adaptively Collected Data: Guarantees for
Supervised and Policy Learning [57.88785630755165]
経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。
本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。
政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
論文 参考訳（メタデータ） (2021-06-03T09:50:13Z) - Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
ガウス過程(GP)は、モデルの不確実性の原理的計算を可能にし、安全性に重要なアプリケーションに魅力的です。
境界付き摂動に対するモデル決定の不変性として定義されるGPの対向的堅牢性を分析するためのフレームワークを提案する。
我々は境界を洗練し、任意の$epsilon > 0$に対して、我々のアルゴリズムが有限個の反復で実際の値に$epsilon$-closeの値に収束することを保証していることを示す分岐とバウンドのスキームを開発する。
論文 参考訳（メタデータ） (2021-04-07T15:14:56Z) - CoinDICE: Off-Policy Confidence Interval Estimation [107.86876722777535]
強化学習における高信頼行動非依存のオフ政治評価について検討する。
様々なベンチマークにおいて、信頼区間推定が既存の手法よりも厳密で精度が高いことが示されている。
論文 参考訳（メタデータ） (2020-10-22T12:39:11Z) - Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation [49.502277468627035]
本稿では,関数近似を用いたバッチデータ強化学習の統計的理論について検討する。
記録履歴から新たな対象政策の累積値を推定するオフ・ポリティクス評価問題を考察する。
論文 参考訳（メタデータ） (2020-02-21T19:20:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。