論文の概要: Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
- arxiv url: http://arxiv.org/abs/2305.08359v1
- Date: Mon, 15 May 2023 05:37:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 16:00:53.538641
- Title: Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
- Title（参考訳）: 逆線形混合MDPにおける水平自由強化学習
- Authors: Kaixuan Ji and Qingyue Zhao and Jiafan He and Weitong Zhang and
Quanquan Gu
- Abstract要約: 我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
- 参考スコア（独自算出の注目度）: 72.40181882916089
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent studies have shown that episodic reinforcement learning (RL) is no
harder than bandits when the total reward is bounded by $1$, and proved regret
bounds that have a polylogarithmic dependence on the planning horizon $H$.
However, it remains an open question that if such results can be carried over
to adversarial RL, where the reward is adversarially chosen at each episode. In
this paper, we answer this question affirmatively by proposing the first
horizon-free policy search algorithm. To tackle the challenges caused by
exploration and adversarially chosen reward, our algorithm employs (1) a
variance-uncertainty-aware weighted least square estimator for the transition
kernel; and (2) an occupancy measure-based technique for the online search of a
\emph{stochastic} policy. We show that our algorithm achieves an
$\tilde{O}\big((d+\log (|\mathcal{S}|^2 |\mathcal{A}|))\sqrt{K}\big)$ regret
with full-information feedback, where $d$ is the dimension of a known feature
mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is
the number of episodes, $|\mathcal{S}|$ and $|\mathcal{A}|$ are the
cardinalities of the state and action spaces. We also provide hardness results
and regret lower bounds to justify the near optimality of our algorithm and the
unavoidability of $\log|\mathcal{S}|$ and $\log|\mathcal{A}|$ in the regret
bound.
- Abstract（参考訳）: 近年の研究では、総報酬が1ドルに制限された場合、RLはバンドイットよりも難しいことが示されており、計画的地平線に多元的依存を持つ後悔境界が$H$であった。
しかし、このような結果が、各エピソードで報酬が逆選択される敵RLに受け継がれるかどうかは、未解決のままである。
本稿では,horizon-free policy searchアルゴリズムを提案することで,この疑問に肯定的に答える。
探索と逆選択された報酬による課題に対処するために,本アルゴリズムでは,(1)変分不確実性を考慮した遷移カーネルの最小2乗推定器,(2)オンライン検索における「emph{stochastic}」ポリシーの占有度測定に基づく手法を用いる。
このアルゴリズムは$\tilde{o}\big((d+\log (|\mathcal{s}|^2 |\mathcal{a}|))\sqrt{k}\big)$を全情報フィードバックで達成できることを示し、ここで$d$はmdpの未知の遷移核を線形にパラメトリする既知の特徴マッピングの次元であり、$k$はエピソード数、$|\mathcal{s}|$および$|\mathcal{a}|$は状態と作用空間の濃度であることを示した。
また、このアルゴリズムの近似最適性と$\log|\mathcal{S}|$と$\log|\mathcal{A}|$の不可避性を正当化するために、難解な結果と後悔の低い境界を与える。
関連論文リスト
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Safe Posterior Sampling for Constrained MDPs with Bounded Constraint
Violation [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、多くのアプリケーションにおいてますます重要になっている複数の目的を持つシーケンシャルな意思決定のシナリオをモデル化する。
我々は,そのような仮定を必要とせず,しかも非常によく機能するSafe PSRL (posterior sample-based RL)アルゴリズムを提案する。
準線形$tildemathcal Oleft(H2.5 sqrt|mathcalS|2 |mathcalA|K right)$上界をベイズ賞の目的的後悔と、有界なイデアルとともに成立させる。
論文 参考訳（メタデータ） (2023-01-27T06:18:25Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。