論文の概要: Asymptotically optimal reinforcement learning in Block Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2510.13748v1
• Date: Wed, 15 Oct 2025 16:54:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-16 20:13:28.77345
• Title: Asymptotically optimal reinforcement learning in Block Markov Decision Processes
• Title（参考訳）: ブロックマルコフ決定過程における漸近的最適強化学習
• Authors: Thomas van Vuren, Fiona Sloothaak, Maarten G. Wolf, Jaron Sanders,
• Abstract要約: 強化学習 (Reinforcement Learning, RL) は、指数関数的に大きな状態と行動空間を持つ実世界の多くの環境では実用的ではない。 クラスタリングを明示的に活用する残念な分析を行い、正確な潜在状態推定が学習を効果的に高速化することを示した。 このアルゴリズムは、クラスタリングの影響を受けやすいBMDPの大規模なクラスで$O(sqrtT+n2)$となる後悔を実現する。
• 参考スコア（独自算出の注目度）: 0.22835610890984168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The curse of dimensionality renders Reinforcement Learning (RL) impractical in many real-world settings with exponentially large state and action spaces. Yet, many environments exhibit exploitable structure that can accelerate learning. To formalize this idea, we study RL in Block Markov Decision Processes (BMDPs). BMDPs model problems with large observation spaces, but where transition dynamics are fully determined by latent states. Recent advances in clustering methods have enabled the efficient recovery of this latent structure. However, a regret analysis that exploits these techniques to determine their impact on learning performance remained open. We are now addressing this gap by providing a regret analysis that explicitly leverages clustering, demonstrating that accurate latent state estimation can indeed effectively speed up learning. Concretely, this paper analyzes a two-phase RL algorithm for BMDPs that first learns the latent structure through random exploration and then switches to an optimism-guided strategy adapted to the uncovered structure. This algorithm achieves a regret that is $O(\sqrt{T}+n)$ on a large class of BMDPs susceptible to clustering. Here, $T$ denotes the number of time steps, $n$ is the cardinality of the observation space, and the Landau notation $O(\cdot)$ holds up to constants and polylogarithmic factors. This improves the best prior bound, $O(\sqrt{T}+n^2)$, especially when $n$ is large. Moreover, we prove that no algorithm can achieve lower regret uniformly on this same class of BMDPs. This establishes that, on this class, the algorithm achieves asymptotic optimality.
• Abstract（参考訳）: 次元性の呪いは、指数関数的に大きな状態と行動空間を持つ実世界の多くの環境で強化学習(RL)を非現実的にする。 しかし、多くの環境は、学習を加速できる悪用可能な構造を示している。 この考え方を定式化するために,ブロックマルコフ決定過程(BMDP)のRLについて検討する。 BMDPは大きな観測空間の問題をモデル化するが、遷移力学は潜在状態によって完全に決定される。 近年のクラスタリング手法の進歩により, この潜伏構造の効率的な回復が可能となった。 しかし、これらの手法を利用して学習性能への影響を判断する後悔の分析は、未解決のままであった。 私たちは現在、クラスタリングを明示的に活用する残念な分析を提供することで、このギャップに対処しています。 具体的には、BMDPの2相RLアルゴリズムを解析し、まずランダム探索により潜伏構造を学習し、その後、その未知構造に適応した楽観的誘導戦略に切り替える。 このアルゴリズムは、クラスタリングの影響を受けやすいBMDPの大規模なクラス上で、$O(\sqrt{T}+n)$である後悔を達成する。 ここで、$T$は時間ステップの数を表し、$n$は観測空間の濃度であり、Landau表記は$O(\cdot)$は定数と多元数因子に比例する。 これにより、$O(\sqrt{T}+n^2)$、特に$n$が大きければ、最前の上限である$O(\sqrt{T}+n^2)$が改善される。 さらに,同じ種類のBMDPでは,アルゴリズムが低い後悔を均一に達成できないことを証明する。 これは、このクラスにおいて、アルゴリズムが漸近的最適性を達成することを証明している。

関連論文リスト

• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation [10.159501412046508]
  マルコフ決定過程(MDP)におけるモデルベース強化学習(RL)について検討する。 我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。 我々の知る限りでは、証明可能な保証付き多項ロジスティック関数近似を用いたモデルベースRLアルゴリズムとしてはこれが初めてである。
  論文  参考訳（メタデータ） (2022-12-27T16:25:09Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)
• Towards Tractable Optimism in Model-Based Reinforcement Learning [37.51073590932658]
  成功させるためには、楽観的なRLアルゴリズムは真の値関数(最適化)を過大に見積もる必要があるが、不正確な(推定誤差)ほどではない。 我々は,これらのスケーラブルな楽観的モデルベースアルゴリズムを,トラクタブルノイズ拡張MDPの解法として再解釈する。 この誤差が低減された場合、楽観的なモデルベースRLアルゴリズムは、連続制御問題における最先端性能と一致することを示す。
  論文  参考訳（メタデータ） (2020-06-21T20:53:19Z)

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

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