論文の概要: Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies
- arxiv url: http://arxiv.org/abs/2203.12922v1
- Date: Thu, 24 Mar 2022 08:14:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-25 14:44:44.999945
- Title: Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies
- Title（参考訳）: 多項式時間における地平線自由強化学習--定常政策の力
- Authors: Zihan Zhang, Xiangyang Ji, Simon S. Du
- Abstract要約: 我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
- 参考スコア（独自算出の注目度）: 88.75843804630772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper gives the first polynomial-time algorithm for tabular Markov
Decision Processes (MDP) that enjoys a regret bound \emph{independent on the
planning horizon}. Specifically, we consider tabular MDP with $S$ states, $A$
actions, a planning horizon $H$, total reward bounded by $1$, and the agent
plays for $K$ episodes. We design an algorithm that achieves an
$O\left(\mathrm{poly}(S,A,\log K)\sqrt{K}\right)$ regret in contrast to
existing bounds which either has an additional $\mathrm{polylog}(H)$
dependency~\citep{zhang2020reinforcement} or has an exponential dependency on
$S$~\citep{li2021settling}. Our result relies on a sequence of new structural
lemmas establishing the approximation power, stability, and concentration
property of stationary policies, which can have applications in other problems
related to Markov chains.
- Abstract（参考訳）: 本稿では,計画地平線に非依存な残差有界なマルコフ決定過程(MDP)に対する最初の多項式時間アルゴリズムを提案する。
具体的には、表型mdpは$s$ステート、$a$アクション、プランニングホライズン$h$、合計報酬は$$$で、エージェントは$k$エピソードでプレイします。
我々は,$O\left(\mathrm{poly}(S,A,\log K)\sqrt{K}\right)$ regretに対して,$O\left(\mathrm{polylog}(H)$ dependency~\citep{zhang2020reinforcement} あるいは$S$~\citep{li2021settling} への指数的依存を持つような既存の境界を持つアルゴリズムを設計する。
この結果は、マルコフ連鎖に関する他の問題に応用できる定常ポリシーの近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
関連論文リスト
- Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal
Algorithm Escaping the Curse of Horizon [88.75843804630772]
エピソード強化学習は文脈的包帯を一般化する。
長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。
MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
論文 参考訳（メタデータ） (2020-09-28T17:52:32Z) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-23T19:30:46Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。