論文の概要: Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

• arxiv url: http://arxiv.org/abs/2608.14319v1
• Date: Fri, 14 Aug 2026 14:04:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 20:14:29.392594
• Title: Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
• Title（参考訳）: 量子多元帯域と線形帯域:低境界とアルゴリズム
• Abstract要約: 量子多重武装バンドイット(QMAB)と量子線形バンドイット(QLB)について検討する。 有限作用 QLB に対して、QMAB に対して $(Klog(T/K))$ および $(dlog(T/d))$ の最初のミニマックス下界を証明する。
• 参考スコア（独自算出の注目度）: 42.57939149964391
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB) in the model of Wan et al. [2023], where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon $T$ with regret $O(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} T)$ for $d$-dimensional QLB. This leaves open whether the $K\log T$ scale is unavoidable and whether the $d^2$ dependence can be improved. We prove the first minimax lower bounds of $Ω(K\log(T/K))$ for QMAB and $Ω(d\log(T/d))$ for finite-action QLB, resolving the question raised by Wan et al. [2023] of whether regret independent of $T$ is achievable. At the heart of our argument is a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives, proved by the polynomial method and a Remez-type inequality for trigonometric polynomials. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. Complementing the lower bounds, we give a design-based elimination algorithm for finite-action QLB. When the action set has size $\operatorname{poly}(d)$, its regret is linear in $d$, improving the prior $d^2$ dependence and matching our lower bound up to polylogarithmic factors. The algorithm couples a low-bias low-variance quantum mean estimator with a small-support $G$-optimal design through a query allocation matched to the design weights. The design-based elimination reduces the dimension dependence from $d^2$ to $d^{3/2}$ when using Quantum Monte Carlo estimates. The low-variance estimator then makes reconstruction error aggregate through variance rather than worst-case absolute error, removing the remaining $\sqrt d$ factor.
• Abstract（参考訳）: We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB) in the model of Wan et al [2023]。 事前の作業は、$O(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} T)$ for $d$-dimensional QLBである。 これにより、$K\log T$スケールが避けられないか、$d^2$依存を改善することができるかが明らかになる。 QMAB に対して $Ω(K\log(T/K))$ と、有限作用 QLB に対して $Ω(d\log(T/d))$ の第一ミニマックス下界を証明し、Wan et al [2023] によって提起された、$T$ から独立な後悔が達成可能であるかどうかという疑問を解決する。 我々の議論の核心は、多項式法と三角多項式に対するRemez型不等式によって証明された、固定報酬平均と代替品の間隔を区別する高信頼の単一腕量子テストの下界である。 バンド・トゥ・テスト・リダクションは QMAB の下界に持ち上げ、線形埋め込みは有限作用 QLB の下界を与える。 下位境界を補完し、有限作用QLBに対する設計に基づく除去アルゴリズムを提案する。 アクションセットのサイズが $\operatorname{poly}(d)$ の場合、その後悔は$d$ で線形であり、以前の $d^2$ 依存を改善し、下位境界をポリ対数因子に一致させる。 このアルゴリズムは、低バイアスの低分散量子平均推定器と、設計重みに一致したクエリ割り当てを通じて、小額の$G$-最適設計とを結合する。 設計に基づく除去は、量子モンテカルロ推定を用いた場合、次元依存を$d^2$から$d^{3/2}$に還元する。 低分散推定器は、最悪の絶対誤差ではなく、分散によって再構成誤差を集約し、残りの$\sqrt d$ factorを除去する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
  for general max-k-XORSAT with $k geq 3$, no-time algorithm can be significantly better than random guessing on worst-case instance。 この接続を明示的にし、任意の有限体上の有界次数$D$および有界次数$E$k$-LINSAT$(q,r)$にハードネスを拡張する。
  論文  参考訳（メタデータ） (2026-06-11T16:59:12Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  我々は、非時間アルゴリズムが任意の定数でランダム割当比$r/q$を超えることを、Hstadの定理から直接還元することで証明する。 この閾値は、デコードされた量子干渉法を規定する半円法則の$ell/mから0$制限と一致する。
  論文  参考訳（メタデータ） (2026-03-04T19:26:26Z)
• Quantum Heavy-tailed Bandits [36.458771174473924]
  重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。 まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。 量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-23T19:23:10Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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