論文の概要: Optimistic PAC Reinforcement Learning: the Instance-Dependent View

• arxiv url: http://arxiv.org/abs/2207.05852v1
• Date: Tue, 12 Jul 2022 21:35:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-14 14:59:13.741475
• Title: Optimistic PAC Reinforcement Learning: the Instance-Dependent View
• Title（参考訳）: 最適PAC強化学習 : インスタンス依存の視点
• Authors: Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann
• Abstract要約: PAC RL, BPI-UCRL に対する楽観的アルゴリズムを提案する。 私たちの限界は、最小の訪問確率を特徴としていますが、それはまた、準最適ギャップという洗練された概念も特徴です。 決定論的遷移を持つMDPでは、BPI-UCRLが実際にはほぼ最適であることを示す。
• 参考スコア（独自算出の注目度）: 24.256960622176305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimistic algorithms have been extensively studied for regret minimization in episodic tabular MDPs, both from a minimax and an instance-dependent view. However, for the PAC RL problem, where the goal is to identify a near-optimal policy with high probability, little is known about their instance-dependent sample complexity. A negative result of Wagenmaker et al. (2021) suggests that optimistic sampling rules cannot be used to attain the (still elusive) optimal instance-dependent sample complexity. On the positive side, we provide the first instance-dependent bound for an optimistic algorithm for PAC RL, BPI-UCRL, for which only minimax guarantees were available (Kaufmann et al., 2021). While our bound features some minimal visitation probabilities, it also features a refined notion of sub-optimality gap compared to the value gaps that appear in prior work. Moreover, in MDPs with deterministic transitions, we show that BPI-UCRL is actually near-optimal. On the technical side, our analysis is very simple thanks to a new "target trick" of independent interest. We complement these findings with a novel hardness result explaining why the instance-dependent complexity of PAC RL cannot be easily related to that of regret minimization, unlike in the minimax regime.
• Abstract（参考訳）: 表層表層MDPの最小化には,ミニマックスとインスタンス依存の両面から最適化アルゴリズムが広く研究されている。 しかしながら、高い確率で最適に近いポリシーを特定することを目的としたpac rl問題では、インスタンス依存のサンプル複雑性についてはほとんど知られていない。 Wagenmaker et al. (2021) の否定的な結果は、楽観的なサンプリング規則は(まだ解明されていない)最適なインスタンス依存のサンプル複雑性を達成するには使えないことを示唆している。 正の面では、pac rl, bpi-ucrlの楽観的アルゴリズムに対する最初のインスタンス依存境界を提供し、minimaxの保証のみを利用可能とした(kaufmann et al., 2021)。 私たちの境界は、訪問確率の最小化を特徴としていますが、以前の作業で現れる値のギャップと比較して、サブオプティリティギャップという洗練された概念も特徴です。 さらに, 決定論的遷移を伴うMDPでは, BPI-UCRLがほぼ最適であることを示す。 技術的な面では、独立した関心の新たな“ターゲットトリック”のおかげで、私たちの分析は非常に単純です。 PAC RLのインスタンス依存的な複雑性が,ミニマックス法とは異なり,後悔の最小化と容易に関連付けられない理由を説明するために,これらの知見を新しい硬さの結果で補完する。

関連論文リスト

• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design [12.056495277232118]
  この研究は、ほぼ最適ポリシーを学ぶことの「インスタンスに依存した」複雑さを理解することを目的としている。 本稿では,複雑性の詳細なインスタンス依存尺度を実現するアルゴリズムである textscPedel を提案する。 我々は、textscPedel が低regret, minimax-optimal アルゴリズムよりも有益であることを示す。
  論文  参考訳（メタデータ） (2022-07-06T10:42:57Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning [29.552894877883883]
  低後悔を達成し、インスタンス最適率で$epsilon$-optimal Policyを特定できるというトレードオフが存在することを示す。 本稿では,このサンプル複雑性を実現する新しい計画ベースアルゴリズムの提案と解析を行う。 我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
  論文  参考訳（メタデータ） (2021-08-05T16:34:17Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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