論文の概要: A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2301.13326v2
• Date: Wed, 11 Oct 2023 23:58:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-14 15:45:28.512369
• Title: A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback
• Title（参考訳）: オフラインアルゴリズムを用いたバンディットフィードバックによる組合せ型多腕バンディット問題の解法
• Authors: Guanyu Nie and Yididiya Y Nadew and Yanhui Zhu and Vaneet Aggarwal and Christopher John Quinn
• Abstract要約: 離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
• 参考スコア（独自算出の注目度）: 27.192028744078282
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of stochastic, combinatorial multi-armed bandits where the learner only has access to bandit feedback and the reward function can be non-linear. We provide a general framework for adapting discrete offline approximation algorithms into sublinear $\alpha$-regret methods that only require bandit feedback, achieving $\mathcal{O}\left(T^\frac{2}{3}\log(T)^\frac{1}{3}\right)$ expected cumulative $\alpha$-regret dependence on the horizon $T$. The framework only requires the offline algorithms to be robust to small errors in function evaluation. The adaptation procedure does not even require explicit knowledge of the offline approximation algorithm -- the offline algorithm can be used as a black box subroutine. To demonstrate the utility of the proposed framework, the proposed framework is applied to diverse applications in submodular maximization. The new CMAB algorithms for submodular maximization with knapsack constraints outperform a full-bandit method developed for the adversarial setting in experiments with real-world data.
• Abstract（参考訳）: 本稿では,学習者が盗聴フィードバックにのみアクセスでき,報酬関数が非線形である確率的,組合せ的マルチアームバンディットの問題について検討する。 離散的オフライン近似アルゴリズムをバンドイットフィードバックのみを必要とする部分線形$\alpha$-regret 法に適用するための一般的なフレームワークを提供し,$\mathcal{o}\left(t^\frac{2}{3}\log(t)^\frac{1}{3}\right)$ 期待累積$\alpha$-regret の水平値$t$ を達成する。 このフレームワークは、関数評価において小さなエラーに対して堅牢なオフラインアルゴリズムを必要とする。 適応手順はオフライン近似アルゴリズムの明示的な知識も必要とせず、オフラインアルゴリズムはブラックボックスサブルーチンとして使うことができる。 提案フレームワークの有用性を示すために,提案フレームワークをサブモジュラー最大化の多様なアプリケーションに適用する。 実世界のデータを用いた実験において,knapsack制約による部分モジュラ最大化のための新しいCMABアルゴリズムは,逆向き設定のために開発されたフルバンド法よりも優れている。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。 非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
  論文  参考訳（メタデータ） (2024-03-15T07:05:44Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。 この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。 近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
  論文  参考訳（メタデータ） (2020-06-01T01:28:44Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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