論文の概要: Nearly Minimax Optimal Reward-free Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2010.05901v2
- Date: Fri, 23 Oct 2020 17:41:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 07:43:49.451246
- Title: Nearly Minimax Optimal Reward-free Reinforcement Learning
- Title（参考訳）: ほぼミニマックスの最適報酬フリー強化学習
- Authors: Zihan Zhang, Simon S. Du, Xiangyang Ji
- Abstract要約: 本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
- 参考スコア（独自算出の注目度）: 88.75843804630772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the reward-free reinforcement learning framework, which is
particularly suitable for batch reinforcement learning and scenarios where one
needs policies for multiple reward functions. This framework has two phases. In
the exploration phase, the agent collects trajectories by interacting with the
environment without using any reward signal. In the planning phase, the agent
needs to return a near-optimal policy for arbitrary reward functions. We give a
new efficient algorithm, \textbf{S}taged \textbf{S}ampling + \textbf{T}runcated
\textbf{P}lanning (\algoname), which interacts with the environment at most
$O\left(
\frac{S^2A}{\epsilon^2}\text{poly}\log\left(\frac{SAH}{\epsilon}\right)
\right)$ episodes in the exploration phase, and guarantees to output a
near-optimal policy for arbitrary reward functions in the planning phase. Here,
$S$ is the size of state space, $A$ is the size of action space, $H$ is the
planning horizon, and $\epsilon$ is the target accuracy relative to the total
reward. Notably, our sample complexity scales only \emph{logarithmically} with
$H$, in contrast to all existing results which scale \emph{polynomially} with
$H$. Furthermore, this bound matches the minimax lower bound
$\Omega\left(\frac{S^2A}{\epsilon^2}\right)$ up to logarithmic factors.
Our results rely on three new techniques : 1) A new sufficient condition for
the dataset to plan for an $\epsilon$-suboptimal policy; 2) A new way to plan
efficiently under the proposed condition using soft-truncated planning; 3)
Constructing extended MDP to maximize the truncated accumulative rewards
efficiently.
- Abstract（参考訳）: 本研究では,バッチ強化学習に特に適する報酬フリー強化学習フレームワークと,複数の報酬関数のポリシーを必要とするシナリオについて検討する。
この枠組みには2つの段階がある。
探索段階では、エージェントは報奨信号を用いずに環境と相互作用して軌道を収集する。
計画段階では、エージェントは任意の報酬関数に対して最適に近いポリシーを返す必要がある。
新しい効率的なアルゴリズムである \textbf{s}taged \textbf{s}ampling + \textbf{t}runcated \textbf{p}lanning (\algoname) を提供し、最大$o\left( \frac{s^2a}{\epsilon^2}\text{poly}\log\left(\frac{sah}{\epsilon}\right) \right)$ episodes in the exploration phase において任意の報酬関数に対して最適に近いポリシーを出力することを保証します。
ここで、$S$は状態空間のサイズ、$A$は行動空間のサイズ、$H$は計画地平線、$\epsilon$は総報酬に対する目標精度である。
特に、サンプル複雑性は、$h$ で \emph{polynomially} をスケールするすべての既存の結果とは対照的に、$h$ で \emph{logarithmically} しかスケールしない。
さらに、この境界はミニマックス下限 $\omega\left(\frac{s^2a}{\epsilon^2}\right)$ から対数因子まで一致する。
1)データセットが$\epsilon$-suboptimal Policyを計画するために必要な新しい条件。
2)ソフトトランク計画を用いた提案条件下での効率的な計画方法
3) 減算した累積報酬を効率的に最大化するために拡張MDPを構築する。
関連論文リスト
- Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - 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) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
探索の課題を分離する「逆フリーなRL」フレームワークを提案する。
我々は,$tildemathcalO(S2Amathrmpoly(H)/epsilon2)$の探索を効率的に行うアルゴリズムを提案する。
また、ほぼ一致する$Omega(S2AH2/epsilon2)$ lower boundを与え、この設定でアルゴリズムのほぼ最適性を示す。
論文 参考訳（メタデータ） (2020-02-07T14:03:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。