論文の概要: 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 Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback [30.23951525723659]
本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
論文 参考訳(メタデータ) (2023-11-14T03:12:43Z) - 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) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳(メタデータ) (2020-10-24T11:02:45Z) - 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) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。