論文の概要: On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs

• arxiv url: http://arxiv.org/abs/2209.02864v1
• Date: Wed, 7 Sep 2022 00:21:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-08 12:01:43.965770
• Title: On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs
• Title（参考訳）: ランダム長エピソードMDPに対するモンテカルロUCBの収束性について
• Authors: Zixuan Dong, Che Wang, Keith Ross
• Abstract要約: 強化学習において、モンテカルロアルゴリズムは、エピソードの戻り値の平均化によってQ関数を更新する。 MC-UCBのQ-函数は最適Q関数にほぼ確実に収束することを示す。 この結果の直接的な結論は、すべての有限ホライゾン MDP に対してほぼ確実に収束するということである。
• 参考スコア（独自算出の注目度）: 3.759936323189418
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In reinforcement learning, Monte Carlo algorithms update the Q function by averaging the episodic returns. In the Monte Carlo UCB (MC-UCB) algorithm, the action taken in each state is the action that maximizes the Q function plus a UCB exploration term, which biases the choice of actions to those that have been chosen less frequently. Although there has been significant work on establishing regret bounds for MC-UCB, most of that work has been focused on finite-horizon versions of the problem, for which each episode terminates after a constant number of steps. For such finite-horizon problems, the optimal policy depends both on the current state and the time within the episode. However, for many natural episodic problems, such as games like Go and Chess and robotic tasks, the episode is of random length and the optimal policy is stationary. For such environments, it is an open question whether the Q-function in MC-UCB will converge to the optimal Q function; we conjecture that, unlike Q-learning, it does not converge for all MDPs. We nevertheless show that for a large class of MDPs, which includes stochastic MDPs such as blackjack and deterministic MDPs such as Go, the Q-function in MC-UCB converges almost surely to the optimal Q function. An immediate corollary of this result is that it also converges almost surely for all finite-horizon MDPs. We also provide numerical experiments, providing further insights into MC-UCB.
• Abstract（参考訳）: 強化学習において、モンテカルロアルゴリズムはエピソディックの戻り値平均化によってq関数を更新する。 モンテカルロ UCB (MC-UCB) アルゴリズムでは、各状態における作用は、Q関数と UCB 探索項を最大化する作用であり、より頻度の低い反応の選択に偏っている。 mc-ucbの後悔の限界を確立する作業は盛んに行われているが、その仕事の大部分は問題の有限ホリゾンバージョンに焦点を当てており、各エピソードは一定数のステップの後に終了する。 このような有限水平問題に対して、最適ポリシーは現在の状態とエピソード内の時間の両方に依存する。 しかし、goやチェス、ロボットタスクといった多くの自然なエピソディクス問題では、エピソードはランダムな長さであり、最適なポリシーは静止している。 そのような環境では、MC-UCB の Q-函数が最適 Q 関数に収束するかどうかが明らかな問題であり、Q-ラーニングとは異なり、全ての MDP に対して収束しないと推測する。 それでも、ブラックジャックのような確率的 MDP や Go のような決定論的 MDP を含む大規模な MDP に対して、MC-UCB の Q-函数はほぼ確実に最適 Q 関数に収束することを示す。 この結果の直接的な結論は、すべての有限ホライゾン MDP に対してほぼ確実に収束するということである。 また、数値実験を行い、MC-UCBに関するさらなる知見を提供する。

関連論文リスト

• Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need [5.283807323380133]
  マルチレベルモンテカルロ(MLCBOC)は標準MC収束率を達成することができる。 理論的研究は、2段階および3段階のルックアヘッド獲得関数の近似改善に焦点を当てている。 本研究は数値的に検証し,いくつかのベンチマーク例でBOに対するCBOCの利点を示す。
  論文  参考訳（メタデータ） (2024-02-03T10:24:30Z)
• Low-Rank MDPs with Continuous Action Spaces [42.695778474071254]
  本研究では,このような手法を連続的な動作を伴う設定に拡張する問題について検討する。 アルゴリズムを変更せずに、動作が連続することを許された場合、同様のPAC境界が得られることを示す。
  論文  参考訳（メタデータ） (2023-11-06T22:05:08Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Learning Logic Specifications for Soft Policy Guidance in POMCP [71.69251176275638]
  部分観測可能なモンテカルロ計画(POMCP)は部分観測可能なマルコフ決定過程(POMDP)の効率的な解法である POMCPはスパース報酬機能、すなわち最終ゴールに達するときのみ得られる報酬に悩まされる。 本稿では,POMCP実行のトレースから論理仕様を学習するために帰納的論理プログラミングを用いる。
  論文  参考訳（メタデータ） (2023-03-16T09:37:10Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection [136.4014229319618]
  線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。 まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
  論文  参考訳（メタデータ） (2021-10-27T22:07:08Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis [24.373900721120286]
  連続的な状態-作用空間を持つ環境でのモンテカルロ計画を考える。 我々は,モンテカルロ計画に連続的な武装バンディット戦略を付加するアルゴリズムであるPoly-HOOTを紹介する。 非定常バンディット問題において,HOOアルゴリズムが拡張されたことを初めて後悔する。
  論文  参考訳（メタデータ） (2020-06-08T15:23:19Z)
• On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning [8.19727735624814]
  強化学習のための単純で自然なアルゴリズムはMonte Carlo Exploring Starts (MCES)である 我々は,元来のより効率的な MCES アルゴリズムを駆使し,最適ポリシーフィードフォワード MDP の収束性をほぼ確実に確立する。 我々は、非常に単純で、大数の強法則のみを利用する、新しい帰納的アプローチを導入する。
  論文  参考訳（メタデータ） (2020-02-10T07:54:57Z)
• Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning [24.956507498394497]
  本稿では,学習に基づくアルゴリズムを用いて,時間依存報酬を用いたマルチエージェント・マルチタスクNPハードプランニング問題をほぼ最適に解決する可能性について検討する。
  論文  参考訳（メタデータ） (2019-05-29T04:02:41Z)

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

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