論文の概要: An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits

• arxiv url: http://arxiv.org/abs/2608.12231v1
• Date: Wed, 12 Aug 2026 16:28:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.636243
• Title: An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits
• Title（参考訳）: 逆数$m$-Set帯域に対する効率的な近似アルゴリズム
• Abstract要約: 各ラウンドで学習者が$d$アイテムから$m$を選択し、選択した項目の総損失のみを観察する。 結果として得られる作用集合は$K=binomdm$要素を含み、したがって指数関数的に大きい。 本稿では,この構造を利用した計算効率のよいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 13.063864592666777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study adversarial combinatorial bandits with $m$-set actions, where at each round the learner selects $m$ out of $d$ items and observes only the aggregate loss of the selected items. The resulting action set contains $K=\binom{d}{m}$ elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same $d$-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least $1-δ$, regret against the best fixed action of \[ R_T = O\left(\sqrt{dT\log(K/δ)}\right). \] This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with $d$ parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al.
• Abstract（参考訳）: そこで,各ラウンドにおいて学習者が$d$アイテムから$m$を選択し,選択した項目の集合的損失のみを観察する。 結果として得られる作用集合は$K=\binom{d}{m}$要素を含み、したがって指数関数的に大きい。 それでも、全てのアクションの損失は、アイテム損失の同じ$d$次元ベクトルによって決定される。 本稿では,この構造を利用した計算効率のよいアルゴリズムを提案する。 適応的非予想の敵に対して、少なくとも1-δ$の確率で、 \[ R_T = O\left(\sqrt{dT\log(K/δ)}\right の最良の固定作用に対する後悔が保証される。 これは Zimmert と Lattimore の有限作用 EXP3-KW アルゴリズムの高確率後悔境界と一致する。 我々のアルゴリズムは、各サンプリング分布を$d$パラメータで表現し、アクションセットを列挙せずに多項式時間で実行する。 したがって、Maitiらによってもたらされるオープンな問題を解く。

関連論文リスト

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  本稿では,学習過程を通じて動作セットをプレフィックスするヘテロセシダスティックノイズによる線形帯域問題を再検討する。 本稿では,情報ゲインを最大化するアクションを積極的に探求する,大規模アクション集合のための分散適応アルゴリズムのtexttVAEEを提案する。 音素平均依存率が避けられないことを示す固定作用集合に対して、ほぼ一致する下界を確立する。
  論文  参考訳（メタデータ） (2026-07-26T14:24:34Z)
• Learning to Sparsify Stochastic Linear Bandits [12.61900668356141]
  本稿では,高次元空間から連続的に行動を選択する線形帯域幅の分散化を学習する問題に対処する。 本稿では,パラメータ学習のための最小二乗法と,スパース動作選択のための特別サブルーチンを用いて,適応的に段階的に探索・利用を行うアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2026-05-11T07:57:37Z)
• An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction [13.78877509090251]
  逆損失とアクションセットを持つ線形文脈帯域に対する効率的なアルゴリズムを提案する。 我々のアルゴリズムは、まず最初に$text(d)sqrtT$後悔を達成するが、事前のアルゴリズムが我々の知識に間に合うように$o(T)$後悔することはない。
  論文  参考訳（メタデータ） (2025-08-16T06:25:18Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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