論文の概要: A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

• arxiv url: http://arxiv.org/abs/2507.22854v1
• Date: Wed, 30 Jul 2025 17:24:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 16:14:18.361478
• Title: A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
• Title（参考訳）: 自由のビットが長い道のり:生成モデルに基づく強化学習のための古典的および量子的アルゴリズム
• Authors: Andris Ambainis, Joao F. Doriguello, Debbie Lim,
• Abstract要約: 有限水平および無限水平平均逆マルコフ決定過程(MDP)を学習するための古典的および量子オンラインアルゴリズムを提案する。 我々のアルゴリズムは、エージェントが生成的サンプリング方式で環境と自由に対話できるハイブリッド探索・生成的強化学習モデルに基づいている。 我々は、RLから「不確実性に直面した最適主義」や「後続サンプリング」といったいくつかのパラダイムを回避し、代わりに最適なポリシーを直接計算し、使用することで、以前の作品と比較して後悔の限界が良くなることを示す。
• 参考スコア（独自算出の注目度）: 0.40964539027092906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose novel classical and quantum online algorithms for learning finite-horizon and infinite-horizon average-reward Markov Decision Processes (MDPs). Our algorithms are based on a hybrid exploration-generative reinforcement learning (RL) model wherein the agent can, from time to time, freely interact with the environment in a generative sampling fashion, i.e., by having access to a "simulator". By employing known classical and new quantum algorithms for approximating optimal policies under a generative model within our learning algorithms, we show that it is possible to avoid several paradigms from RL like "optimism in the face of uncertainty" and "posterior sampling" and instead compute and use optimal policies directly, which yields better regret bounds compared to previous works. For finite-horizon MDPs, our quantum algorithms obtain regret bounds which only depend logarithmically on the number of time steps $T$, thus breaking the $O(\sqrt{T})$ classical barrier. This matches the time dependence of the prior quantum works of Ganguly et al. (arXiv'23) and Zhong et al. (ICML'24), but with improved dependence on other parameters like state space size $S$ and action space size $A$. For infinite-horizon MDPs, our classical and quantum bounds still maintain the $O(\sqrt{T})$ dependence but with better $S$ and $A$ factors. Nonetheless, we propose a novel measure of regret for infinite-horizon MDPs with respect to which our quantum algorithms have $\operatorname{poly}\log{T}$ regret, exponentially better compared to classical algorithms. Finally, we generalise all of our results to compact state spaces.
• Abstract（参考訳）: 有限水平および無限水平平均逆マルコフ決定過程(MDP)を学習するための古典的および量子オンラインアルゴリズムを提案する。 提案アルゴリズムは, エージェントが生成的サンプリング方式で環境と自由に対話できるハイブリッド探索・生成強化学習(RL)モデルに基づく。 学習アルゴリズム内の生成モデルの下で最適なポリシを近似するために、既知の古典的および新しい量子アルゴリズムを用いることで、「不確実性に直面した最適化」や「後続サンプリング」といったRLからのいくつかのパラダイムを回避し、代わりに最適なポリシを直接計算し、使用することにより、以前の研究と比べて後悔の限界が良くなることを示す。 有限ホライゾン MDP に対して、我々の量子アルゴリズムは、時間ステップ数$T$に対数的にのみ依存する残差境界を求め、従って$O(\sqrt{T})$古典障壁を破る。 これはGanguly et al (arXiv'23) と Zhong et al (ICML'24) の以前の量子研究の時間依存性と一致するが、状態空間サイズ$S$やアクション空間サイズ$A$といった他のパラメータへの依存性が改善されている。 無限水平 MDP に対して、我々の古典的および量子的境界は依然として$O(\sqrt{T})$依存を維持しているが、より優れた$S$と$A$因子を持つ。 それにもかかわらず、我々の量子アルゴリズムは、古典的アルゴリズムよりも指数関数的に良い $\operatorname{poly}\log{T}$ を持つという、無限水平 MDP に対する新たな後悔の尺度を提案する。 最後に、全ての結果をコンパクトな状態空間に一般化する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
  量子強化学習(RL)のための新しいUCRL型アルゴリズムを提案する。 我々は$mathcalO(mathrmpoly(S, A, H, log T))$ the worst-case regret for it, where $T$ is the number of episodes。 具体的には、$d$次元線形表現を持つ線形混合MDPに対する値目標回帰(VTR)に基づく量子アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-21T16:23:11Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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