論文の概要: Efficient Swap Regret Minimization in Combinatorial Bandits

• arxiv url: http://arxiv.org/abs/2602.02087v1
• Date: Mon, 02 Feb 2026 13:34:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.168861
• Title: Efficient Swap Regret Minimization in Combinatorial Bandits
• Title（参考訳）: コンビニアルバンドにおける効率的なスワップレグレスト最小化
• Authors: Andreas Kontogiannis, Vasilis Pollatos, Panayotis Mertikopoulos, Ioannis Panageas,
• Abstract要約: 本稿は,N$のアクション数が指数関数的に大きいバンディットに対して,効率的な非スワップ後悔アルゴリズムを設計する問題に対処する。 我々は,N$で複数対数的にスケールし,盗賊のクラスには厳格な,無洗脳学習アルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 33.43176196113965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions $N$ is exponentially large in the dimensionality of the problem. In this setting, designing efficient no-swap regret translates to sublinear -- in horizon $T$ -- swap regret with polylogarithmic dependence on $N$. In contrast to the weaker notion of external regret minimization - a problem which is fairly well understood in the literature - achieving no-swap regret with a polylogarithmic dependence on $N$ has remained elusive in combinatorial bandits. Our paper resolves this challenge, by introducing a no-swap-regret learning algorithm with regret that scales polylogarithmically in $N$ and is tight for the class of combinatorial bandits. To ground our results, we also demonstrate how to implement the proposed algorithm efficiently -- that is, with a per-iteration complexity that also scales polylogarithmically in $N$ -- across a wide range of well-studied applications.
• Abstract（参考訳）: 本論文は, 組合せ帯域に対する効率的な非スワップ後悔アルゴリズムを設計する問題に対処するものである。 この設定では、効率的なノースワップの後悔を設計することは -- 水平線$T$で -- に変換する。 外部の後悔の最小化というより弱い概念とは対照的に、文献でかなりよく理解されている問題であり、N$に対する多対数的依存を伴って無言の後悔を達成している。 本稿は,N$で多対数的にスケールし,組合せ帯域幅のクラスに密着した,非スワップ回帰学習アルゴリズムを導入することで,この問題を解決している。 我々はまた,提案アルゴリズムを効率よく実装する方法,すなわち,多対数的に$N$でスケールする点当たりの複雑性を,広範囲のよく研究されたアプリケーションに対して示す。

関連論文リスト

• Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games [43.12477663757647]
  Lu et al., [2025] による最近の研究は、コンパレータ $phi$ に対する後悔が、ある疎度ベースの複雑性尺度$phi$ に依存する適応アルゴリズムを導入している。 本研究では,より単純なアルゴリズムを用いて,より優れたコンパレータ適応型$Phi$-regretバウンドを実現するための一般的なアイデアを提案する。
  論文  参考訳（メタデータ） (2025-05-22T20:45:47Z)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
  我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。 提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-23T08:07:54Z)
• 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)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Online Linear Optimization with Many Hints [72.4277628722419]
  本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。 この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2020-10-06T23:25:05Z)

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

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