Fugu-MT 論文翻訳(概要): A Doubly Robust Approach to Sparse Reinforcement Learning

論文の概要: A Doubly Robust Approach to Sparse Reinforcement Learning

arxiv url: http://arxiv.org/abs/2310.15286v1
Date: Mon, 23 Oct 2023 18:52:17 GMT
ステータス: 処理完了
システム内更新日: 2023-10-25 22:12:53.209373
Title: A Doubly Robust Approach to Sparse Reinforcement Learning
Title（参考訳）: スパース強化学習への二重ロバストなアプローチ
Authors: Wonyoung Kim and Garud Iyengar and Assaf Zeevi
Abstract要約: エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
参考スコア（独自算出の注目度）: 19.68978899041642
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a new regret minimization algorithm for episodic sparse linear Markov decision process (SMDP) where the state-transition distribution is a linear function of observed features. The only previously known algorithm for SMDP requires the knowledge of the sparsity parameter and oracle access to an unknown policy. We overcome these limitations by combining the doubly robust method that allows one to use feature vectors of \emph{all} actions with a novel analysis technique that enables the algorithm to use data from all periods in all episodes. The regret of the proposed algorithm is $\tilde{O}(\sigma^{-1}_{\min} s_{\star} H \sqrt{N})$, where $\sigma_{\min}$ denotes the restrictive the minimum eigenvalue of the average Gram matrix of feature vectors, $s_\star$ is the sparsity parameter, $H$ is the length of an episode, and $N$ is the number of rounds. We provide a lower regret bound that matches the upper bound up to logarithmic factors on a newly identified subclass of SMDPs. Our numerical experiments support our theoretical results and demonstrate the superior performance of our algorithm.
Abstract（参考訳）: 状態遷移分布が観測された特徴の線形関数であるエピソドックススパース線形マルコフ決定過程(smdp)に対する新たな後悔最小化アルゴリズムを提案する。 SMDPの唯一の既知のアルゴリズムは、疎度パラメータと未知のポリシーへのオラクルアクセスの知識を必要とする。これらの制限を克服するために,各エピソードのすべての周期からのデータを利用する新しい解析手法と,\emph{all} アクションの特徴ベクトルを併用する2つのロバストな手法を提案する。提案アルゴリズムの後悔は$\tilde{o}(\sigma^{-1}_{\min} s_{\star} h \sqrt{n})$であり、ここで$\sigma_{\min}$ は特徴ベクトルの平均グラム行列の最小固有値、$s_\star$ はスパーシティパラメータ、$h$ はエピソードの長さ、$n$ はラウンド数である。新たに同定されたSMDPのサブクラスにおいて,上界から対数的因子までを一致させる低い後悔境界を提供する。我々の数値実験は理論的な結果をサポートし,アルゴリズムの優れた性能を示す。

関連論文リスト

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)
Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T14:37:21Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
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)
Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文参考訳（メタデータ） (2020-02-29T02:02:40Z)

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

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