論文の概要: Online Markov Decision Processes with Non-oblivious Strategic Adversary
- arxiv url: http://arxiv.org/abs/2110.03604v1
- Date: Thu, 7 Oct 2021 16:32:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-08 15:55:59.725093
- Title: Online Markov Decision Processes with Non-oblivious Strategic Adversary
- Title（参考訳）: 非公開戦略対応型オンラインマルコフ決定プロセス
- Authors: Le Cong Dinh, David Henry Mguni, Long Tran-Thanh, Jun Wang, Yaodong
Yang
- Abstract要約: オンラインマルコフ決定過程 (OMDP) において, 損失関数は非公開の戦略的敵によって選択される。
MDP-Expertは、暗黙の敵とうまく連携する既存のアルゴリズムで、$mathcalO(sqrtTlog(L)+tau2sqrt T log(|A|))$のポリシー後悔の限界を達成でき、$L$は敵の純粋な戦略セットのサイズであり、$|A|$はサイズを表す。
- 参考スコア（独自算出の注目度）: 35.25621843666453
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a novel setting in Online Markov Decision Processes (OMDPs) where
the loss function is chosen by a non-oblivious strategic adversary who follows
a no-external regret algorithm. In this setting, we first demonstrate that
MDP-Expert, an existing algorithm that works well with oblivious adversaries
can still apply and achieve a policy regret bound of $\mathcal{O}(\sqrt{T
\log(L)}+\tau^2\sqrt{ T \log(|A|)})$ where $L$ is the size of adversary's pure
strategy set and $|A|$ denotes the size of agent's action space. Considering
real-world games where the support size of a NE is small, we further propose a
new algorithm: MDP-Online Oracle Expert (MDP-OOE), that achieves a policy
regret bound of $\mathcal{O}(\sqrt{T\log(L)}+\tau^2\sqrt{ T k \log(k)})$ where
$k$ depends only on the support size of the NE. MDP-OOE leverages the key
benefit of Double Oracle in game theory and thus can solve games with
prohibitively large action space. Finally, to better understand the learning
dynamics of no-regret methods, under the same setting of no-external regret
adversary in OMDPs, we introduce an algorithm that achieves last-round
convergence result to a NE. To our best knowledge, this is first work leading
to the last iteration result in OMDPs.
- Abstract（参考訳）: オンラインマルコフ決定過程 (omdps) における新たな設定について検討し, 損失関数は非外的後悔アルゴリズムに従う非聖書的戦略敵によって選択される。
この設定では、既存のアルゴリズムである MDP-Expert が依然として適用可能であることを初めて証明し、$\mathcal{O}(\sqrt{T \log(L)}+\tau^2\sqrt{T \log(|A|)})$ のポリシー再帰を達成でき、$L$ は敵の純粋な戦略セットのサイズであり、$|A|$ はエージェントのアクション空間のサイズを表す。
MDP-Online Oracle Expert (MDP-OOE) は, NEのサポートサイズが小さい実世界のゲームを考えると, NEのサポートサイズのみに依存する$\mathcal{O}(\sqrt{T\log(L)}+\tau^2\sqrt{T k \log(k)})$である。
MDP-OOEはゲーム理論においてDouble Oracleの重要な利点を生かし、したがって違法に大きなアクション空間を持つゲームを解くことができる。
最後に,no-regret法の学習ダイナミクスをよりよく理解するために,omdpsにおけるno-external regret adversaryと同じ設定下で,neへの最終収束結果を達成するアルゴリズムを提案する。
私たちの知る限りでは、これがOMDPの最終イテレーション結果につながる最初の作業です。
関連論文リスト
- 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) - A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。
提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文 参考訳（メタデータ） (2023-10-23T18:52:17Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $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。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
論文 参考訳（メタデータ） (2022-11-27T20:38:47Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。