論文の概要: Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions
- arxiv url: http://arxiv.org/abs/2101.07957v2
- Date: Sat, 27 Feb 2021 11:22:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-22 01:34:16.700269
- Title: Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions
- Title（参考訳）: 線形ペイオフ関数を有するコンビネートコンビネート半帯域に対する近似的後悔境界
- Authors: Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro
Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
- Abstract要約: 我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 53.77572276969548
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The contextual combinatorial semi-bandit problem with linear payoff functions
is a decision-making problem in which a learner chooses a set of arms with the
feature vectors in each round under given constraints so as to maximize the sum
of rewards of arms. Several existing algorithms have regret bounds that are
optimal with respect to the number of rounds $T$. However, there is a gap of
$\tilde{O}(\max(\sqrt{d}, \sqrt{k}))$ between the current best upper and lower
bounds, where $d$ is the dimension of the feature vectors, $k$ is the number of
the chosen arms in a round, and $\tilde{O}(\cdot)$ ignores the logarithmic
factors. The dependence of $k$ and $d$ is of practical importance because $k$
may be larger than $T$ in real-world applications such as recommender systems.
In this paper, we fill the gap by improving the upper and lower bounds. More
precisely, we show that the C${}^2$UCB algorithm proposed by Qin, Chen, and Zhu
(2014) has the optimal regret bound $\tilde{O}(d\sqrt{kT} + dk)$ for the
partition matroid constraints. For general constraints, we propose an algorithm
that modifies the reward estimates of arms in the C${}^2$UCB algorithm and
demonstrate that it enjoys the optimal regret bound for a more general problem
that can take into account other objectives simultaneously. We also show that
our technique would be applicable to related problems. Numerical experiments
support our theoretical results and considerations.
- Abstract（参考訳）: 線形ペイオフ関数を用いた文脈組合せ半帯域問題(英: contextual combinatorial semi-bandit problem)は、学習者が与えられた制約の下で各ラウンドに特徴ベクトルを持つ一組のアームを選択し、武器の報酬の総和を最大化する決定問題である。
いくつかの既存のアルゴリズムは、ラウンド数に対して最適な後悔の限界を持っている。
しかし、現在の最高上限と下限の間には$\tilde{o}(\max(\sqrt{d}, \sqrt{k})$の差があり、ここで$d$は特徴ベクトルの次元、$k$はラウンド内の選択されたアームの数、$\tilde{o}(\cdot)$は対数因子を無視している。
なぜなら、$k$はレコメンダシステムのような現実世界のアプリケーションでは$T$よりも大きいかもしれないからである。
本稿では,上界と下界を改善することでギャップを埋める。
より正確には、Qin, Chen, Zhu (2014) によって提案された C${}^2$UCB アルゴリズムは、分割マトロイドの制約に対して、最適の後悔束 $\tilde{O}(d\sqrt{kT} + dk)$ を持つことを示す。
一般的な制約に対して,C${}^2$UCBアルゴリズムのアームの報酬推定を修正したアルゴリズムを提案し,他の目的を同時に考慮可能な,より一般的な問題に対する最適の後悔境界を満足することを示した。
また,本手法が関連する問題に適用できることを示す。
数値実験は理論的結果と考察を支援する。
関連論文リスト
- LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:30:37Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。