論文の概要: Regret Bounds for Quantum Linear Bandits
- arxiv url: http://arxiv.org/abs/2611.15237v1
- Date: Wed, 11 Nov 2026 09:29:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.09256
- Title: Regret Bounds for Quantum Linear Bandits
- Title(参考訳): 量子線形帯域のレグレト境界
- Abstract要約: 有界報酬を持つ$d$次元量子線型帯域について検討する。
一般的なアクション集合に対して、既存のアルゴリズムは後悔の$O(d3/2operatornamepolylog(T))$ over $T$ ラウンドを達成する。
- 参考スコア(独自算出の注目度): 42.57939149964391
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study $d$-dimensional quantum linear bandits with bounded rewards, where the learner selects an action and queries its quantum reward oracle or its inverse in each round. For general action sets, existing algorithms achieve regret $O(d^{3/2}\operatorname{polylog}(T))$ over $T$ rounds. Prior work established a lower bound of $Ω(d\log(1+T/d))$, leaving open whether the $d^{3/2}$ dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of $Ω(d^{3/2}\log(1+T/d^{3/2}))$. To prove this result, we construct a family of hard instances in which the reward gap of each action is proportional to its squared distance from the optimal action. We establish a posterior Fisher information bound for adaptive quantum queries with quantum memory, relating the information acquired about the optimal direction to the regret incurred. Viewing each selected action as an estimate of the optimal direction, we use a matrix Cramér--Rao argument to derive a lower bound on expected regret. When the action set is fixed and has size $K$, we propose two phased elimination algorithms, Soft-G-Elim and QG-Elim. We adapt quantum phase estimation to construct SoftQME, a mean estimator with small bias and controlled tails. Soft-G-Elim estimates the mean reward of every surviving action from independent SoftQME outputs on the support of an experimental design. Controlling the bias and fluctuations of these estimates yields regret $O(d\log T\log(dT)\sqrt{\log(KT)})$, reducing the $\log(KT)\log\log(dT)$ factor in the previous regret bound to $\sqrt{\log(KT)}$. QG-Elim further reduces this factor to $\min\{\sqrt{\log(KT)},\sqrt d\}$.
- Abstract(参考訳): そこで,学習者が行動を選択し,各ラウンドで量子報酬のオラクルやその逆を問う。
一般的なアクション集合に対して、既存のアルゴリズムは後悔の$O(d^{3/2}\operatorname{polylog}(T))$ over $T$ roundsを達成する。
以前の研究は$Ω(d\log(1+T/d))$という下界を確立し、上界の$d^{3/2}$依存が必要とされるかどうかを問わない。
この問題は、$Ω(d^{3/2}\log(1+T/d^{3/2}))$のミニマックス下限を証明することで解決する。
この結果を証明するために、各アクションの報酬ギャップが最適なアクションから2乗距離に比例するハードインスタンスの族を構築する。
我々は、量子メモリを用いた適応量子クエリーにバウンドされた後続のフィッシャー情報を確立する。
選択された各作用を最適方向の推定として見た場合、行列のクラメール-ラオ論法を用いて、期待される後悔に対する低い境界を導出する。
アクションセットが固定され、サイズが$K$の場合には、Soft-G-ElimとQG-Elimの2つの段階的除去アルゴリズムを提案する。
我々は、小さなバイアスと制御されたテールを持つ平均推定器であるSoftQMEを構築するために量子位相推定を適用する。
Soft-G-Elimは、実験的な設計の支持に基づいて、独立したSoftQME出力から生き残ったすべてのアクションの平均報酬を見積もる。
これらの推定のバイアスとゆらぎを制御すると、後悔の$O(d\log T\log(dT)\sqrt{\log(KT)})$となり、前回の後悔の$\log(KT)\log\log(dT)$ factorを$\sqrt{\log(KT)}$に制限する。
QG-Elimはこの因子をさらに$\min\{\sqrt{\log(KT)},\sqrt d\}$に還元する。
関連論文リスト
- Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits [24.0850778188305]
我々は、$K$アクション、$N$ポリシーのクラス、すなわち学習者がサンプリングできる分布からコンテキストを学習する。
プレー前に固定された損失関数の任意の列に対して、実現されたコンテキストを考慮に入れた最良のポリシーに対して、期待された後悔の$O(sqrtKTlog (2N),log (2KT)$のオラクル効率のアルゴリズムを与える。
論文 参考訳(メタデータ) (2026-11-12T17:04:36Z) - Closing the Log Gap: Minimax-Optimal Regret for Episodic RL [13.138763447728417]
我々は,$big(H3 SAlog(frac1)varepsilon-2big)$ minimax lower のアルゴリズムを開発した。
また、$varepsilon, )$-PACベスト政治識別アルゴリズムも開発しており、これは最初に$big(H3 SAlog(frac1)varepsilon-2big)$ minimax lower bound up to constants in some regimesと一致する。
論文 参考訳(メタデータ) (2026-10-29T14:38:15Z) - High-Probability Regret Bounds for Feel-Good Thompson Sampling [50.91983233376599]
フィールグッドトンプソンサンプリング(FGTS)は、バニラトンプソンサンプリングの後部を、高い予測最適値の報酬関数を求める探索項で強化する。
コンテクスト的包帯における累積FGTSと現在のステップFGTSの両方に対する最初の高い確率的後悔境界を導出する。
期待された信頼の保証とは対照的に、後悔を高い確率で制御するコストは加法項に制限される。
論文 参考訳(メタデータ) (2026-10-14T03:30:45Z) - Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms [42.57939149964391]
量子多重武装バンドイット(QMAB)と量子線形バンドイット(QLB)について検討する。
有限作用 QLB に対して、QMAB に対して $(Klog(T/K))$ および $(dlog(T/d))$ の最初のミニマックス下界を証明する。
論文 参考訳(メタデータ) (2026-08-14T14:04:21Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳(メタデータ) (2026-07-28T09:29:37Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳(メタデータ) (2022-10-20T21:32:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。