Fugu-MT 論文翻訳(概要): Multi-Play Combinatorial Semi-Bandit Problem

論文の概要: Multi-Play Combinatorial Semi-Bandit Problem

arxiv url: http://arxiv.org/abs/2509.09933v1
Date: Fri, 12 Sep 2025 02:46:59 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-15 16:03:07.960853
Title: Multi-Play Combinatorial Semi-Bandit Problem
Title（参考訳）: Multi-Play Combinatorial Semi-Bandit 問題
Authors: Shintaro Nakamura, Yuko Kuroki, Wei Chen,
Abstract要約: 半帯域(CSB)問題において、プレイヤーはアクションセットからアクションを選択し、アクションに含まれるベースアームからのフィードバックを観察する。マルチプレイ・セミバンド (MP-CSB) を提案し、プレイヤーは非負の整数アクションを選択し、各ラウンドで1つの腕から複数のフィードバックを観測できる。
参考スコア（独自算出の注目度）: 8.922365714546162
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the combinatorial semi-bandit (CSB) problem, a player selects an action from a combinatorial action set and observes feedback from the base arms included in the action. While CSB is widely applicable to combinatorial optimization problems, its restriction to binary decision spaces excludes important cases involving non-negative integer flows or allocations, such as the optimal transport and knapsack problems.To overcome this limitation, we propose the multi-play combinatorial semi-bandit (MP-CSB), where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round. We propose two algorithms for the MP-CSB. One is a Thompson-sampling-based algorithm that is computationally feasible even when the action space is exponentially large with respect to the number of arms, and attains $O(\log T)$ distribution-dependent regret in the stochastic regime, where $T$ is the time horizon. The other is a best-of-both-worlds algorithm, which achieves $O(\log T)$ variance-dependent regret in the stochastic regime and the worst-case $\tilde{\mathcal{O}}\left( \sqrt{T} \right)$ regret in the adversarial regime. Moreover, its regret in adversarial one is data-dependent, adapting to the cumulative loss of the optimal action, the total quadratic variation, and the path-length of the loss sequence. Finally, we numerically show that the proposed algorithms outperform existing methods in the CSB literature.
Abstract（参考訳）: 組み合わせセミバンドイット(CSB)問題において、プレイヤーは、組み合わせアクションセットからアクションを選択し、アクションに含まれるベースアームからのフィードバックを観察する。 CSBは組合せ最適化問題に広く適用されているが、バイナリ決定空間に対する制限は、最適輸送やknapsack問題などの非負の整数フローやアロケーションを含む重要なケースを除外しており、この制限を克服するために、プレイヤーが非負の整数アクションを選択し、各ラウンドで単一のアームから複数のフィードバックを観測できるマルチプレイ組合せ半帯域(MP-CSB)を提案する。本稿では,MP-CSBの2つのアルゴリズムを提案する。一つはトンプソンサンプリングに基づくアルゴリズムで、アクション空間が腕の数に関して指数関数的に大きい場合でも計算可能であり、確率的状態においてO(\log T)$分布依存的後悔を達成できる。もう1つは、確率的状態における$O(\log T)$分散依存的後悔と、対数的状態における$\tilde{\mathcal{O}}\left( \sqrt{T} \right)$後悔を達成できるベスト・オブ・ワールドのアルゴリズムである。さらに、逆数に対する後悔はデータ依存であり、最適動作の累積損失、全2次変動、損失シーケンスの経路長に適応する。最後に,提案手法がCSB文献の既存手法より優れていることを示す。

関連論文リスト

Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
論文参考訳（メタデータ） (2025-04-09T22:07:01Z)
Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
論文参考訳（メタデータ） (2025-03-01T21:25:21Z)
Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文参考訳（メタデータ） (2024-02-23T08:07:54Z)
Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文参考訳（メタデータ） (2023-12-13T11:08:25Z)
Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文参考訳（メタデータ） (2023-10-02T08:15:52Z)
A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
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)
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)

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

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