論文の概要: Improved Regret Bounds for Linear Adversarial MDPs via Linear
Optimization
- arxiv url: http://arxiv.org/abs/2302.06834v1
- Date: Tue, 14 Feb 2023 05:15:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 16:19:30.264323
- Title: Improved Regret Bounds for Linear Adversarial MDPs via Linear
Optimization
- Title（参考訳）: リニア最適化による線形逆MDPのレギュレット境界の改善
- Authors: Fang Kong, Xiangcheng Zhang, Baoxiang Wang, Shuai Li
- Abstract要約: 対戦環境におけるマルコフ決定過程(MDP)の学習は困難である。
線形敵対的MDPに対する最先端の結果は、$tildeO(K6/7)$$(K$はエピソード数を表す)を後悔する。
線形最適化の帯域分割アームの特徴マップを微妙に設定することにより,線形 MDP を線形最適化に還元する新しい視点の問題点を考察する。
- 参考スコア（独自算出の注目度）: 19.09749538491176
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning Markov decision processes (MDP) in an adversarial environment has
been a challenging problem. The problem becomes even more challenging with
function approximation, since the underlying structure of the loss function and
transition kernel are especially hard to estimate in a varying environment. In
fact, the state-of-the-art results for linear adversarial MDP achieve a regret
of $\tilde{O}(K^{6/7})$ ($K$ denotes the number of episodes), which admits a
large room for improvement. In this paper, we investigate the problem with a
new view, which reduces linear MDP into linear optimization by subtly setting
the feature maps of the bandit arms of linear optimization. This new technique,
under an exploratory assumption, yields an improved bound of
$\tilde{O}(K^{4/5})$ for linear adversarial MDP without access to a transition
simulator. The new view could be of independent interest for solving other MDP
problems that possess a linear structure.
- Abstract（参考訳）: 対戦環境におけるマルコフ決定過程(MDP)の学習は困難である。
この問題は、損失関数と遷移核の基底構造は、様々な環境では特に推定が難しいため、関数近似によりさらに困難になる。
実際、線形敵対的MDPの最先端の結果は、$\tilde{O}(K^{6/7})$$(K$はエピソード数を表す)を後悔する結果となり、改善の余地は大きい。
本稿では,線形最適化のバンディットアームの特徴マップを部分的に設定することにより,線形mdpを線形最適化に還元する新しい視点で問題を検討する。
この新しい手法は、探索的な仮定のもと、遷移シミュレーターにアクセスせずに、線形逆mdpに対して$\tilde{o}(k^{4/5})$の上限を改善する。
新しい見解は、線形構造を持つ他のMDP問題の解決に独立した関心を持つかもしれない。
関連論文リスト
- Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
本稿では,無限水平平均逆線形混合マルコフ決定過程(MDPs)を学習するための計算抽出可能なアルゴリズムを提案する。
線形混合MDPのアルゴリズムは,$widetildemathcalO(dsqrtmathrmsp(v*)T)$$$T$以上の最小限の後悔上限を実現する。
論文 参考訳（メタデータ） (2024-10-19T05:45:50Z) - A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。
これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。
我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
論文 参考訳（メタデータ） (2024-10-14T12:10:06Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement
Learning in Discounted Linear MDPs [16.006893624836554]
本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。
VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。
後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
論文 参考訳（メタデータ） (2023-10-17T18:27:27Z) - A Theoretical Analysis of Optimistic Proximal Policy Optimization in
Linear Markov Decision Processes [13.466249082564213]
本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。
既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
論文 参考訳（メタデータ） (2023-05-15T17:55:24Z) - Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。
また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
論文 参考訳（メタデータ） (2023-02-24T05:14:27Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Nonstationary Reinforcement Learning with Linear Function Approximation [19.521419943509784]
ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。
まず、周期的再起動を伴う最小二乗値の楽観的な修正を開発し、変動予算が分かっている場合にその動的後悔を束縛する。
非定常線型 MDP に対する最初の minimax dynamic regret lower bound を導出し、副生成物として Jin らによって未解決の線型 MDP に対する minimax regret lower bound を定めている。
論文 参考訳（メタデータ） (2020-10-08T20:07:44Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。