論文の概要: Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback
- arxiv url: http://arxiv.org/abs/2311.07876v1
- Date: Tue, 14 Nov 2023 03:12:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 15:43:48.316208
- Title: Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback
- Title（参考訳）: 未知の遷移と全情報フィードバックを用いた対向的低ランクマルコフ決定過程の学習
- Authors: Canzhe Zhao, Ruofeng Yang, Baoxiang Wang, Xuezhou Zhang, Shuai Li
- Abstract要約: 本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
- 参考スコア（独自算出の注目度）: 30.23951525723659
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study the low-rank MDPs with adversarially changed losses in
the full-information feedback setting. In particular, the unknown transition
probability kernel admits a low-rank matrix decomposition \citep{REPUCB22}, and
the loss functions may change adversarially but are revealed to the learner at
the end of each episode. We propose a policy optimization-based algorithm POLO,
and we prove that it attains the
$\widetilde{O}(K^{\frac{5}{6}}A^{\frac{1}{2}}d\ln(1+M)/(1-\gamma)^2)$ regret
guarantee, where $d$ is rank of the transition kernel (and hence the dimension
of the unknown representations), $A$ is the cardinality of the action space,
$M$ is the cardinality of the model class, and $\gamma$ is the discounted
factor. Notably, our algorithm is oracle-efficient and has a regret guarantee
with no dependence on the size of potentially arbitrarily large state space.
Furthermore, we also prove an $\Omega(\frac{\gamma^2}{1-\gamma} \sqrt{d A K})$
regret lower bound for this problem, showing that low-rank MDPs are
statistically more difficult to learn than linear MDPs in the regret
minimization setting. To the best of our knowledge, we present the first
algorithm that interleaves representation learning, exploration, and
exploitation to achieve the sublinear regret guarantee for RL with nonlinear
function approximation and adversarial losses.
- Abstract（参考訳）: 本研究では,全情報フィードバック設定において,逆向きに損失が変化する低ランクMPPについて検討する。
特に、未知遷移確率カーネルは低ランク行列分解 \citep{REPUCB22} を許容し、損失関数は逆向きに変化するが、各エピソードの最後に学習者に明らかにされる。
我々は、ポリシー最適化に基づくアルゴリズムポロを提案し、そのアルゴリズムが$\widetilde{o}(k^{\frac{5}{6}}a^{\frac{1}{2}}d\ln(1+m)/(1-\gamma)^2)$となることを証明する。
特に、我々のアルゴリズムはオラクル効率が高く、潜在的に大きな状態空間のサイズに依存しない残念な保証を持っている。
さらに、この問題に対して$\Omega(\frac{\gamma^2}{1-\gamma} \sqrt{d A K})$ regret lower bound を証明し、低ランクの MDP は、後悔最小化設定において線形の MDP よりも統計的に学習することが困難であることを示す。
我々の知識を最大限に活用するために, 表現学習, 探索, 活用をインターリーブし, 非線形関数近似と逆損失を伴うrlの劣線形後悔保証を実現する最初のアルゴリズムを提案する。
関連論文リスト
- Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。
本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
論文 参考訳（メタデータ） (2024-11-05T13:55:52Z) - The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure [9.631640936820126]
多くの強化学習アルゴリズムは、問題の状態と行動空間のA$であるSが大きすぎるため、実際に使用するには高すぎる。
我々は、ソースとターゲットのMDPが遷移カーネルを持つ場合、遅延低ランク表現を転送する問題を考察する。
提案アルゴリズムは,各ソースMDPの潜在表現を学習し,その線形構造を利用して,ターゲットMDPの後悔境界における$S,A$,あるいは$SA$への依存を除去する。
論文 参考訳（メタデータ） (2024-10-28T23:12:08Z) - A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。
提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文 参考訳（メタデータ） (2023-10-23T18:52:17Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。