論文の概要: Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
- arxiv url: http://arxiv.org/abs/2605.09277v2
- Date: Tue, 12 May 2026 03:42:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-13 18:21:07.026335
- Title: Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
- Title（参考訳）: 睡眠半バンドにおけるコンビニアルトンプソンサンプリングのための最悪値レグレクト境界
- Authors: Zhiming Huang, Bingshan Hu, Jianping Pan,
- Abstract要約: 睡眠時腕を有する半バンド患者に対するCTS(Thompson sample)の最悪の再検討を行った。
CL-SGは単純なCTS-G変種であり、各ラウンドで1つの共有ガウス種をサンプリングし、腕間の探索を協調する。
CL-SG は $tildeO(sqrtmNT)$ の改善された後悔境界と一致する低い境界 $(sqrtmNT)$ を達成することを示す。
- 参考スコア（独自算出の注目度）: 6.725466985159166
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We revisit combinatorial Thompson sampling (CTS) for semi-bandits with sleeping arms, where arm availability varies over time and actions must satisfy combinatorial constraints, as in wireless mesh routing with fluctuating link availability. Despite its practical relevance, CTS has been hindered by several long-standing problems: (i) the absence of worst-case regret guarantees in the semi-bandit setting even without sleeping arms, (ii) the lack of theory under adversarially varying availability, and (iii) the consistently weak empirical performance of CTS with Gaussian priors (CTS-G). This paper resolves these long-standing issues by providing the first worst-case regret analysis of CTS-G, proving an upper bound of $\tilde{O}(m\sqrt{NT})$ and a matching lower bound of $\tildeΩ(m\sqrt{NT})$. To bridge the gap between theory and practice, we further propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. We show that CL-SG achieves an improved regret bound of $\tilde{O}(\sqrt{mNT})$, together with a matching lower bound $Ω(\sqrt{mNT})$. Experiments on real-world datasets demonstrate that CL-SG consistently outperforms strong baselines including CTS-G and CTS-B, and we open-source our implementation for reproducibility.
- Abstract（参考訳）: 睡眠時アーム付き半バンド用組み合わせ型トンプソンサンプリング (CTS) について検討し, 腕の可利用性は時間とともに変化し, 動作は結合性制約を満たす必要があることを示した。
現実的な関連性にもかかわらず、CTSはいくつかの長年の問題に悩まされてきた。
一 寝た腕なしでも半団結状態にある最悪の後悔の保証がないこと。
(二)反対に利用可能な理論の欠如、及び
3) ガウス前駆体(CTS-G)を用いたCTSの一貫して弱い経験的性能。
本稿では、CTS-G の最悪の再帰解析を初めて提供し、上限が $\tilde{O}(m\sqrt{NT})$ と、一致する下限が $\tildeΩ(m\sqrt{NT})$ であることを示す。
理論と実践のギャップを埋めるため、CL-SGについても提案する。CL-SGは単純なCTS-Gの変種で、各ラウンドで1つの共有ガウス種をサンプリングし、腕間の探索を調整する。
CL-SG は $\tilde{O}(\sqrt{mNT})$ と一致する下界 $Ω(\sqrt{mNT})$ を改良された後悔境界とすることを示した。
実世界のデータセットでの実験では、CL-SGはCTS-GやCTS-Bといった強力なベースラインを一貫して上回り、再現性の実装をオープンソースにしています。
関連論文リスト
- Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits [5.873949143662286]
複数の基地局(BSs)が複数の単一アンテナ用ユーザ機器(UEs)に、UE毎に一意なビームと離散データ伝送速度で接続するマルチユーザmmWave MISOシステムにおいて、ダウンリンクビームとレート適応について検討する。
サービス目標を符号化するために、整合スループットしきい値$_r$を導入し、ビームレート境界を超える半帯域として、鋳造継手ビームとレート適応を導入する。
SAT-CTSは,ユーザ間の平均スループットと公平性を良好に達成しつつ,常に後悔を減らし,競争標準の後悔を維持していることを示す。
論文 参考訳（メタデータ） (2026-04-16T11:49:51Z) - Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
KL正規化目標に対するオンライン学習の統計的効率について検討する。
我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
論文 参考訳（メタデータ） (2026-03-02T18:17:33Z) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - When Combinatorial Thompson Sampling meets Approximation Regret [7.538482310185135]
マルチアームバンディット問題(CMAB)に対するコンビニアルトンプソンサンプリングポリシー(CTS)について検討する。
近似オラクルの特定の条件下で得られた CTS に対して,最初の $mathcalO(log(T)/Delta)$ approximation regret upperbound を提供する。
論文 参考訳（メタデータ） (2023-02-22T07:27:59Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳（メタデータ） (2020-11-05T05:16:04Z) - Statistical Efficiency of Thompson Sampling for Combinatorial
Semi-Bandits [56.31950477139053]
半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討
我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。
この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
論文 参考訳（メタデータ） (2020-06-11T17:12:11Z) - A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
論文 参考訳（メタデータ） (2020-02-12T18:54:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。