論文の概要: Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

• arxiv url: http://arxiv.org/abs/2102.04692v1
• Date: Tue, 9 Feb 2021 07:46:34 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-10 14:59:12.988412
• Title: Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Title（参考訳）: 適応マルチステップブートストラップによるタブラMDPの細粒ギャップ依存性境界
• Authors: Haike Xu, Tengyu Ma, Simon S. Du
• Abstract要約: 本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
• 参考スコア（独自算出の注目度）: 84.66885506098724
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-dependent regret bound. The first innovation is to estimate the optimal $Q$-function by combining an optimistic bootstrap with an adaptive multi-step Monte Carlo rollout. The second innovation is to select the action with the largest confidence interval length among admissible actions that are not dominated by any other actions. We show when each state has a unique optimal action, AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. In contrast, Simchowitz and Jamieson (2019) showed all upper-confidence-bound (UCB) algorithms suffer an additional $\Omega\left(\frac{S}{\Delta_{min}}\right)$ regret due to over-exploration where $\Delta_{min}$ is the minimum sub-optimality gap and $S$ is the number of states. We further show that for general MDPs, AMB suffers an additional $\frac{|Z_{mul}|}{\Delta_{min}}$ regret, where $Z_{mul}$ is the set of state-action pairs $(s,a)$'s satisfying $a$ is a non-unique optimal action for $s$. We complement our upper bound with a lower bound showing the dependency on $\frac{|Z_{mul}|}{\Delta_{min}}$ is unavoidable for any consistent algorithm. This lower bound also implies a separation between reinforcement learning and contextual bandits.
• Abstract（参考訳）: 本稿では, より強いギャップ依存的後悔境界を満足する, 有限水平マルコフ決定過程(MDP, Adaptive Multi-step Bootstrap, AMB)のモデルフリーアルゴリズムを提案する。 最初のイノベーションは、楽観的なブートストラップと適応的なマルチステップモンテカルロロールアウトを組み合わせることで、最適な$Q$関数を推定することです。 第2のイノベーションは、他のアクションに支配されない許容されるアクションのうち、最大信頼区間長のアクションを選択することである。 我々は、各状態が固有の最適作用を有する場合、AMBは、サブオプティマティリティギャップの逆の合計でのみスケールするギャップ依存の後悔の境界を達成します。 対照的に、Simchowitz と Jamieson (2019) は、すべての上限値(UCB)アルゴリズムが、過剰探索により、$\Delta_{min}$ が最小の準最適ギャップであり、$S$ が状態数であるために、追加の$\Omega\left(\frac{S}{\Delta_{min}}\right)$ 後悔することを示した。 さらに、一般の MDP に対して AMB は追加の $\frac{|Z_{mul}|}{\Delta_{min}}$ に苦しむことを示し、ここで $Z_{mul}$ は状態-作用対 $(s,a)$ の満足する $a$ の集合は $s$ の非一様最適作用である。 我々は、任意の一貫したアルゴリズムに対して、$\frac{|z_{mul}|}{\delta_{min}}$ への依存性が避けられないことを示す下限で上限を補う。 この下限はまた、強化学習と文脈的包帯の分離を意味する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [41.20252349191698]
  部分的な監視は、限られたフィードバックを伴うオンライン意思決定問題の一般的なフレームワークである。 ハイブリッド正規化器を用いたExOの新しいフレームワークと解析法を提案する。 特に、$O(sum_a neq a*)$で、$k$、$m$、$T$はアクション、観察、ラウンドの数である。
  論文  参考訳（メタデータ） (2024-02-13T09:34:22Z)
• 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)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
  UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。 さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
  論文  参考訳（メタデータ） (2020-10-01T17:57:47Z)

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

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