論文の概要: Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
- arxiv url: http://arxiv.org/abs/2508.06247v1
- Date: Fri, 08 Aug 2025 12:01:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-11 20:39:06.217922
- Title: Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
- Title（参考訳）: 能率的確率的半帯域に対する準最適レグレット
- Authors: Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li,
- Abstract要約: Minimax Optimal Strategy (CMOSS) は、半帯域フィードバックの下で$Obig(log k)2sqrtkmTbig )$のインスタンスに依存しない後悔を実現する。
CMOSSは、残念なランタイムと効率の両方でベンチマークアルゴリズムを一貫して上回っていることを示す。
- 参考スコア（独自算出の注目度）: 12.655523567240042
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The combinatorial multi-armed bandit (CMAB) is a cornerstone of sequential decision-making framework, dominated by two algorithmic families: UCB-based and adversarial methods such as follow the regularized leader (FTRL) and online mirror descent (OMD). However, prominent UCB-based approaches like CUCB suffer from additional regret factor $\log T$ that is detrimental over long horizons, while adversarial methods such as EXP3.M and HYBRID impose significant computational overhead. To resolve this trade-off, we introduce the Combinatorial Minimax Optimal Strategy in the Stochastic setting (CMOSS). CMOSS is a computationally efficient algorithm that achieves an instance-independent regret of $O\big( (\log k)^2\sqrt{kmT}\big )$ under semi-bandit feedback, where $m$ is the number of arms and $k$ is the maximum cardinality of a feasible action. Crucially, this result eliminates the dependency on $\log T$ and matches the established $\Omega\big( \sqrt{kmT}\big)$ lower bound up to $O\big((\log k)^2\big)$. We then extend our analysis to show that CMOSS is also applicable to cascading feedback. Experiments on synthetic and real-world datasets validate that CMOSS consistently outperforms benchmark algorithms in both regret and runtime efficiency.
- Abstract（参考訳）: CMAB(Commerintorial Multi-armed bandit)は、UCBに基づく、正規化リーダ(FTRL)やオンラインミラー降下(OMD)といった敵対的手法の2つのアルゴリズムによって支配される、シーケンシャルな意思決定フレームワークの基盤である。
しかし、CUCBのようなUCBベースの顕著なアプローチは、長い地平線上で有害な$\log T$の追加の後悔要因に悩まされ、EXP3.MやHYBRIDのような敵対的な手法は計算上のオーバーヘッドを著しく引き起こす。
このトレードオフを解決するために,我々は,Stochastic setting (CMOSS) における Combinatorial Minimax Optimal Strategyを導入する。
CMOSSは、半帯域フィードバックの下で、$O\big( (\log k)^2\sqrt{kmT}\big )$のインスタンス非依存の後悔を達成する計算効率の良いアルゴリズムである。
重要なことに、この結果は$\log T$への依存を排除し、確立された$\Omega\big( \sqrt{kmT}\big)$ lower bound up to $O\big((\log k)^2\big)$と一致する。
次に解析を拡張して、CMOSSがカスケードフィードバックにも適用可能であることを示す。
合成および実世界のデータセットの実験は、CMOSSが後悔と実行効率の両方でベンチマークアルゴリズムを一貫して上回っていることを検証している。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [41.20252349191698]
部分的な監視は、限られたフィードバックを伴うオンライン意思決定問題の一般的なフレームワークである。
ハイブリッド正規化器を用いたExOの新しいフレームワークと解析法を提案する。
特に、$O(sum_a neq a*)$で、$k$、$m$、$T$はアクション、観察、ラウンドの数である。
論文 参考訳（メタデータ） (2024-02-13T09:34:22Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。