論文の概要: Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design

• arxiv url: http://arxiv.org/abs/2207.02575v2
• Date: Thu, 20 Jul 2023 12:59:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-21 19:07:24.130040
• Title: Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
• Title（参考訳）: オンライン実験設計による線形MDPのインスタンス依存ニア最適ポリシー同定
• Authors: Andrew Wagenmaker, Kevin Jamieson
• Abstract要約: この研究は、ほぼ最適ポリシーを学ぶことの「インスタンスに依存した」複雑さを理解することを目的としている。 本稿では,複雑性の詳細なインスタンス依存尺度を実現するアルゴリズムである textscPedel を提案する。 我々は、textscPedel が低regret, minimax-optimal アルゴリズムよりも有益であることを示す。
• 参考スコア（独自算出の注目度）: 12.056495277232118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL) -- the complexity of learning on the "worst-case" instance -- such measures of complexity often do not capture the true difficulty of learning. In practice, on an "easy" instance, we might hope to achieve a complexity far better than that achievable on the worst-case instance. In this work we seek to understand the "instance-dependent" complexity of learning near-optimal policies (PAC RL) in the setting of RL with linear function approximation. We propose an algorithm, \textsc{Pedel}, which achieves a fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that \textsc{Pedel} yields provable gains over low-regret, minimax-optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on a novel online experiment design-based procedure which focuses the exploration budget on the "directions" most relevant to learning a near-optimal policy, and may be of independent interest.
• Abstract（参考訳）: 強化学習(RL)のミニマックスサンプル複雑性("Worst-case"インスタンスでの学習の複雑さ)を理解するために多くの進歩があったが、そのような複雑さの尺度は学習の真の困難を捉えていないことが多い。 実際、"簡単"なインスタンスでは、最悪のケースで達成可能なものよりもはるかに複雑なものを達成することを望んでいます。 本研究は,線形関数近似を用いたRLの設定において,ニア最適化ポリシー(PAC RL)を学習する際の「インスタンス依存」の複雑さを理解することを目的とする。 本稿では,関数近似設定付きrlにおいて,その1つ目となる,複雑性のきめ細かなインスタンス依存測度を実現するアルゴリズムである \textsc{pedel} を提案する。 明示的な例を通して,低regret,minimax-Optimalアルゴリズムよりも証明可能なゲインが得られ,そのようなアルゴリズムがインスタンス最適化率に到達できないことを示す。 提案手法は, 探索予算を, 最適に近い政策の学習に最も関係のある「方向」に着目し, 独立した興味を持ったオンライン実験手法に依拠する。

関連論文リスト

• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Optimistic PAC Reinforcement Learning: the Instance-Dependent View [24.256960622176305]
  PAC RL, BPI-UCRL に対する楽観的アルゴリズムを提案する。 私たちの限界は、最小の訪問確率を特徴としていますが、それはまた、準最適ギャップという洗練された概念も特徴です。 決定論的遷移を持つMDPでは、BPI-UCRLが実際にはほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2022-07-12T21:35:03Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  本稿では、オフラインデータやデモ、あるいは既存のポリシーを使ってRLポリシーを初期化するメタアルゴリズムを提案する。 特に,タスク解決に2つのポリシーを利用するアルゴリズムであるJump-Start Reinforcement Learning (JSRL)を提案する。 実験により、JSRLは既存の模倣と強化学習アルゴリズムを大幅に上回っていることを示す。
  論文  参考訳（メタデータ） (2022-04-05T17:25:22Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning [29.552894877883883]
  低後悔を達成し、インスタンス最適率で$epsilon$-optimal Policyを特定できるというトレードオフが存在することを示す。 本稿では,このサンプル複雑性を実現する新しい計画ベースアルゴリズムの提案と解析を行う。 我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
  論文  参考訳（メタデータ） (2021-08-05T16:34:17Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization [21.879621917722613]
  政策空間の一般化を伴う大規模強化学習(RL)問題における最適なサンプル複雑性について検討する。 既存の結果は、一般化モデルがなければ、RLアルゴリズムのサンプルの複雑さは必然的に状態空間と行動空間の濃度に依存することを示している。 本稿では,政策学習の本質的な複雑さを特徴付ける,政策空間におけるユーラダー次元の新たな概念を提案する。
  論文  参考訳（メタデータ） (2020-08-17T14:26:18Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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