論文の概要: Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

• arxiv url: http://arxiv.org/abs/2605.30976v1
• Date: Fri, 29 May 2026 08:17:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-01 20:56:50.463557
• Title: Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
• Title（参考訳）: 1ビット通信制約付きバッチ確率線形帯域
• Abstract要約: 制限なしの線形バンディットに対するミニマックスの後悔にほぼ一致するように、バッチ毎のフィードバックは1ビットに1つしかありません。 我々は、$G$-elimination設計と1ビット平均推定に基づく2つの位相除去アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 27.994941928937802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size $B$, and during each batch the learner sends $B$ requested arm pulls to an agent, who then observes the corresponding $B$ rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that $Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})$ regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of $\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})$. We develop two phased-elimination algorithms based on $G$-optimal designs and 1-bit mean estimation. The first achieves $\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(Ω(d))$, and the second incorporates a safe-arm identification and warm-start procedure to obtain $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, which is near-optimal in broad scaling regimes of $(\lvert \mathcal{A} \rvert, B, d, T)$. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as $Θ(\sqrt{T})$.
• Abstract（参考訳）: 我々は,バッチ処理と通信制約の自然な組み合わせの下で確率線形帯域について検討する:時間水平線は等しい大きさのバッチに分割され,各バッチ中に学習者がB$要求アームをエージェントに送信し,対応するB$報酬を観察し,学習者に1ビットのフィードバックで応答する。 各バッチに対して、学習者は、エージェントが使用する1ビットの量子化ルールを指定する。 この設定は、ラウンド単位の量子化のみまたは全ビット予算のみを持つ以前のモデルの間の重要な「中間基底」に対処する。 我々は、ノイズがなくても1ビットの通信ボトルネックのため、$Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})$ regretが避けられないことを示すミニマックス下界を確立する。 標準統計限界と組み合わせると、これは$\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})$の一般下界が得られる。 我々は、G$-optimal designと1ビット平均推定に基づく2つの位相除去アルゴリズムを開発した。 1つは$\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(Ω(d))$、もう1つは$\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, これは、$(\lvert \mathcal{A} \rvert, B, T)の幅広いスケールにおいて、ほぼ最適である。 以上の結果から, 大規模スケールでは, 1バッチあたり1ビットのフィードバックが, 制限のないリニアブレイディットに対するミニマックスの後悔とほぼ一致し, バッチサイズが$ >(\sqrt{T})$ に大きければよいことを示した。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits [21.76698452732286]
  空間と適応性に制約を同時に与えたマルチアームバンディットについて検討する。 我々は、$W$-bitメモリ制約を持つアルゴリズムは、少なくとも$(K/W)$バッチを使用して、最小限の後悔である$widetildeO(sqrtKT)$を達成する必要があることを証明している。
  論文  参考訳（メタデータ） (2026-03-14T04:02:50Z)
• Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach [26.085126064745378]
  そこでは,N$エージェントが協力してグローバルな平均損失を最小限に抑えつつ,ローカルな損失のみを観察する。 この問題のミニマックス後悔は$tilde(sqrt(-1/2+K/N)T)$であり、$T$は地平線、$K$は行動の数、$は通信行列のスペクトルギャップである。
  論文  参考訳（メタデータ） (2026-02-06T05:53:38Z)
• Stochastic Linear Bandits with Parameter Noise [36.09200986359924]
  ここでは、水平方向の$T$に対する$widetildeO (sqrtd T log (K/) 2_max)$、次元$d$の$K$の一般的なアクションセット、そして、$_max$が任意のアクションに対する報酬の最大分散であることを示す。 驚くべきことに、この最適(対数的要因による)後悔境界は、非常に単純な探索探索アルゴリズムを用いて達成可能であることを示す。
  論文  参考訳（メタデータ） (2026-01-30T16:47:42Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
  限定適応性の制約内における一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
  論文  参考訳（メタデータ） (2024-04-10T08:47:57Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators [23.313461266708877]
  置換行列 $bPitrue$ とスパース信号 $bbetatrue$ をシャッフルラベルから再構成する。 提案した推定器は, 穏やかな条件下で, 基本トラス$(bPitrue, supp(bbetatrue))$が得られることを示す。
  論文  参考訳（メタデータ） (2023-03-20T16:14:58Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。 textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
  論文  参考訳（メタデータ） (2021-10-26T04:06:51Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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