論文の概要: Accelerating Linear Bandits with Persistent Candidate Sets

• arxiv url: http://arxiv.org/abs/2610.13407v1
• Date: Fri, 09 Oct 2026 11:20:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.549757
• Title: Accelerating Linear Bandits with Persistent Candidate Sets
• Title（参考訳）: 永続的候補集合による線形帯域加速
• Abstract要約: 楽観的な楽観的なスコアリングは、大きな固定セットのK$アクションを持つ線形バンディットにおいて、アクション選択にコストがかかる可能性がある。 我々は、$k$のアクティブアクションを維持し、$q$のチャレンジャーを均一にサンプリングするPersistent Candidate LinUCB(textscPC-LinUCB)を紹介する。 実験の結果、textscPC-LinUCBはLinUCBを著しく加速し、同等の後悔を維持していることがわかった。
• 参考スコア（独自算出の注目度）: 11.219134218519686
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-LinUCB}), which maintains $k$ active actions and samples $q$ challengers uniformly from the remaining $K-k$ actions at each round. By scoring only these $k+q$ candidates, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{O}(k+q)$. We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.
• Abstract（参考訳）: 楽観的な楽観的なスコアリングは、1ラウンドあたり$\mathcal{O}(K)$スコア評価を必要とする大きな固定セットのK$アクションを持つ線形バンディットにおいて、アクション選択にコストがかかる可能性がある。 我々は,各ラウンドの残りの$K-k$アクションから$k$のアクティブアクションと$q$チャレンジャーを均一にサンプリングするPersistent Candidate LinUCB(\textsc{PC-LinUCB})を紹介する。 これらの$k+q$の候補のみを採点することで、 \textsc{PC-LinUCB} はラウンド当たりのスコア評価を $\mathcal{O}(k+q)$ に減らす。 我々は、標準線形帯域学習項と次数$\mathcal{O}\left((K-k)\log(K-k)/q\right)$の付加的な発見コストからなる問題非依存かつ問題依存の高確率後悔境界を確立する。 特に、この追加コストは地平線で増加しない。 固定ギャップと十分に長い地平線に対して、均一な挑戦者サンプリングの下で、$Ω\left((K-k)/q\right)$ regret lower boundを確立し、部分的候補アクセス自体が避けられない後悔のコストを課すことを示した。 実験により、textsc{PC-LinUCB}はLinUCBと同等の後悔を維持しながら実質的に加速し、永続的な候補機構がLinUCBを超えて拡張できることが示されている。

関連論文リスト

• Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
  我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。 コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
  論文  参考訳（メタデータ） (2026-09-23T22:25:52Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits [13.075031222564535]
  マルチアームのバンディットアルゴリズムは、後悔によって評価されるが、同等の後悔は、独立ラン毎に異なるアロケーションと共存することができる。 我々は、最低ケースの後悔$mathcalR_K,T$と不安定$mathcalS_K,T$のトレードオフを、端末プルカウントの最大の標準偏差として定義し、$K$アームと$T$ラウンドについて検討する。
  論文  参考訳（メタデータ） (2026-08-18T14:38:47Z)
• Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret [1.0098114696565863]
  待ち時間後悔は、学習者の待ち時間とオラクルの待ち時間の間に期待される差として定義される。 本稿では,この値を$widetildemathcalO(T-1/2)$に改善する。
  論文  参考訳（メタデータ） (2026-06-08T15:51:25Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  KL正規化目標に対するオンライン学習の統計的効率について検討する。 我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
  論文  参考訳（メタデータ） (2026-03-02T18:17:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Truncated LinUCB for Stochastic Linear Bandits [7.0879234284391455]
  LinUCBアルゴリズムは、関連する線形帯域に最適に近い最小値である。 LinUCBのtruncatedバージョンが提案され、Tr-LinUCBと呼ばれている。
  論文  参考訳（メタデータ） (2022-02-23T19:01:27Z)
• 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)

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

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