本稿では、有限地平線と無限地平線平均補償マルコフ意思決定プロセス（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の新しい後悔指標を提案します。最後に、すべての結果をコンパクトな状態空間に一般化します。
