論文の概要: Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using
Online Function Approximation
- arxiv url: http://arxiv.org/abs/2303.01464v1
- Date: Thu, 2 Mar 2023 18:27:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 13:08:03.514643
- Title: Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using
Online Function Approximation
- Title（参考訳）: オンライン関数近似を用いた逆文脈mdpの効率的なレート最適後悔
- Authors: Orin Levy, Alon Cohen, Asaf Cassel, Yishay Mansour
- Abstract要約: 我々は,敵対的文脈 MDP における後悔最小化のためのOMG-CMDP!アルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオンライン回帰オラクルを仮定する)、近似誤差に対して単純で堅牢である。
- 参考スコア（独自算出の注目度）: 48.98020692698762
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present the OMG-CMDP! algorithm for regret minimization in adversarial
Contextual MDPs. The algorithm operates under the minimal assumptions of
realizable function class and access to online least squares and log loss
regression oracles. Our algorithm is efficient (assuming efficient online
regression oracles), simple and robust to approximation errors. It enjoys an
$\widetilde{O}(H^{2.5} \sqrt{ T|S||A| ( \mathcal{R}(\mathcal{O}) + H
\log(\delta^{-1}) )})$ regret guarantee, with $T$ being the number of episodes,
$S$ the state space, $A$ the action space, $H$ the horizon and
$\mathcal{R}(\mathcal{O}) = \mathcal{R}(\mathcal{O}_{\mathrm{sq}}^\mathcal{F})
+ \mathcal{R}(\mathcal{O}_{\mathrm{log}}^\mathcal{P})$ is the sum of the
regression oracles' regret, used to approximate the context-dependent rewards
and dynamics, respectively. To the best of our knowledge, our algorithm is the
first efficient rate optimal regret minimization algorithm for adversarial
CMDPs that operates under the minimal standard assumption of online function
approximation.
- Abstract（参考訳）: 我々は,敵対的文脈 MDP における後悔最小化のためのOMG-CMDP!アルゴリズムを提案する。
このアルゴリズムは、実現可能な関数クラスとオンライン最小二乗およびログロス回帰オラクルへのアクセスの最小仮定の下で動作する。
我々のアルゴリズムは効率的であり(効率的なオンライン回帰オラクルを仮定する)、近似誤差に対して単純で堅牢である。
これは$\widetilde{O}(H^{2.5} \sqrt{T|S|A| ( \mathcal{R}(\mathcal{O})) + H \log(\delta^{-1}) )})$ regret guarantee, with $T$ is the number of episodes, $S$ the state space, $A$ the action space, $H$ the horizon, $\mathcal{R}(\mathcal{O}) = \mathcal{R}(\mathcal{O}_{\mathrm{sq}}^\mathcal{F}) + \mathcal{R}(\mathcal{O}_{\mathrm{log}}^\mathcal{P})$$ $T$は、それぞれ退行の和であり、相似的、相似的、相似的、相似的、相似的、相似的、相似的、相似的、相似的、相似的、相似的。
私たちの知る限りでは、オンライン関数近似の最小標準仮定の下で動作する敵cmdpに対する、最初の効率的なレート最適後悔最小化アルゴリズムである。
関連論文リスト
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。
注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文 参考訳（メタデータ） (2024-06-03T11:53:44Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。
非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。
我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - 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) - 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) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Optimism in Face of a Context: Regret Guarantees for Stochastic
Contextual MDP [46.86114958340962]
我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。
我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
論文 参考訳（メタデータ） (2022-07-22T15:00:15Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。