Fugu-MT 論文翻訳(概要): Refined Regret for Adversarial MDPs with Linear Function Approximation

論文の概要: Refined Regret for Adversarial MDPs with Linear Function Approximation

arxiv url: http://arxiv.org/abs/2301.12942v2
Date: Thu, 1 Jun 2023 22:43:47 GMT
ステータス: 処理完了
システム内更新日: 2023-06-05 20:08:27.602878
Title: Refined Regret for Adversarial MDPs with Linear Function Approximation
Title（参考訳）: 線形関数近似を用いた逆MDPの精製レグレット
Authors: Yan Dai, Haipeng Luo, Chen-Yu Wei, Julian Zimmert
Abstract要約: 我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 50.00022394876222
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider learning in an adversarial Markov Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes and the state space can be arbitrarily large. We assume that the Q-function of any policy is linear in some known features, that is, a linear function approximation exists. The best existing regret upper bound for this setting (Luo et al., 2021) is of order $\tilde{\mathcal O}(K^{2/3})$ (omitting all other dependencies), given access to a simulator. This paper provides two algorithms that improve the regret to $\tilde{\mathcal O}(\sqrt K)$ in the same setting. Our first algorithm makes use of a refined analysis of the Follow-the-Regularized-Leader (FTRL) algorithm with the log-barrier regularizer. This analysis allows the loss estimators to be arbitrarily negative and might be of independent interest. Our second algorithm develops a magnitude-reduced loss estimator, further removing the polynomial dependency on the number of actions in the first algorithm and leading to the optimal regret bound (up to logarithmic terms and dependency on the horizon). Moreover, we also extend the first algorithm to simulator-free linear MDPs, which achieves $\tilde{\mathcal O}(K^{8/9})$ regret and greatly improves over the best existing bound $\tilde{\mathcal O}(K^{14/15})$. This algorithm relies on a better alternative to the Matrix Geometric Resampling procedure by Neu & Olkhovskaya (2020), which could again be of independent interest.
Abstract（参考訳）: 我々は,mdp(adversarial markov decision process)において,損失関数がk$エピソード以上で任意に変化し,状態空間が任意に大きくなるような学習を考える。任意の方針の q-函数は、ある既知の特徴、すなわち線型関数近似において線型であると仮定する。この設定に対する最大の後悔の上界(Luo et al., 2021)は、シミュレータへのアクセスを条件に、$\tilde{\mathcal O}(K^{2/3})$(他のすべての依存関係を省略)である。本稿では,同じ設定で$\tilde{\mathcal O}(\sqrt K)$に対する後悔を改善する2つのアルゴリズムを提案する。我々の最初のアルゴリズムは、FTRLアルゴリズムをログバリア正規化器を用いて精巧に解析する。この分析により、損失推定者は任意に負であり、独立した関心を持つことができる。第2のアルゴリズムは、マグニチュード低減損失推定器を開発し、第1のアルゴリズムのアクション数に対する多項式依存性をさらに取り除き、(対数項と水平線への依存性まで)最適な後悔境界へと導く。さらに、最初のアルゴリズムをシミュレータフリーな線形MDPに拡張し、$\tilde{\mathcal O}(K^{8/9})を後悔し、$\tilde{\mathcal O}(K^{14/15})$に対して大幅に改善する。このアルゴリズムは、neu & olkhovskaya (2020) による行列幾何学的再サンプリング手順のより良い代替法に依存している。

関連論文リスト

Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
ベルマン最適条件下で線形マルコフ決定過程(MDP)と線形混合MDPを学習するアルゴリズムを提案する。線形MDPに対する我々のアルゴリズムは、$widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$タイムステップの最もよく知られた後悔の上限を達成する。線形混合 MDP に対して、我々のアルゴリズムは、$widetildemathcalO(dcdotmathrm) の後悔境界に達する。
論文参考訳（メタデータ） (2024-09-16T23:13:42Z)
Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文参考訳（メタデータ） (2024-06-03T11:53:44Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文参考訳（メタデータ） (2023-12-24T08:27:30Z)
A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文参考訳（メタデータ） (2023-10-23T18:52:17Z)
Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文参考訳（メタデータ） (2023-02-22T20:21:25Z)
Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文参考訳（メタデータ） (2022-12-12T18:58:59Z)
Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文参考訳（メタデータ） (2021-02-17T18:54:08Z)
Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [95.80683238546499]
本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。 Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
論文参考訳（メタデータ） (2021-02-15T02:08:39Z)
Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文参考訳（メタデータ） (2020-07-23T08:23:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。