論文の概要: Combinatorial Multi-armed Bandits: Arm Selection via Group Testing

• arxiv url: http://arxiv.org/abs/2410.10679v1
• Date: Mon, 14 Oct 2024 16:19:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-29 20:15:14.970496
• Title: Combinatorial Multi-armed Bandits: Arm Selection via Group Testing
• Title（参考訳）: Combinatorial Multi-armed Bandits: グループテストによるアーム選択
• Authors: Arpan Mukherjee, Shashanka Ubaru, Keerthiram Murugesan, Karthikeyan Shanmugam, Ali Tajer,
• Abstract要約: 本稿では、半帯域フィードバックとスーパーアームサイズに対する濃度制約を備えたマルチアームバンディットの問題について考察する。 この問題を解決するための既存のアルゴリズムは、2つの重要なサブルーチンを含むのが一般的である。 本稿では, 完全オラクルに代わる新しい現実的な代替案を紹介する。
• 参考スコア（独自算出の注目度）: 36.24836468586544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the problem of combinatorial multi-armed bandits with semi-bandit feedback and a cardinality constraint on the super-arm size. Existing algorithms for solving this problem typically involve two key sub-routines: (1) a parameter estimation routine that sequentially estimates a set of base-arm parameters, and (2) a super-arm selection policy for selecting a subset of base arms deemed optimal based on these parameters. State-of-the-art algorithms assume access to an exact oracle for super-arm selection with unbounded computational power. At each instance, this oracle evaluates a list of score functions, the number of which grows as low as linearly and as high as exponentially with the number of arms. This can be prohibitive in the regime of a large number of arms. This paper introduces a novel realistic alternative to the perfect oracle. This algorithm uses a combination of group-testing for selecting the super arms and quantized Thompson sampling for parameter estimation. Under a general separability assumption on the reward function, the proposed algorithm reduces the complexity of the super-arm-selection oracle to be logarithmic in the number of base arms while achieving the same regret order as the state-of-the-art algorithms that use exact oracles. This translates to at least an exponential reduction in complexity compared to the oracle-based approaches.
• Abstract（参考訳）: 本稿では,半帯域フィードバックとスーパーアームサイズに対する濃度制約を併用した複合型マルチアームバンディットの問題について考察する。 既存のアルゴリズムでは、(1)ベースアームパラメータの集合を逐次推定するパラメータ推定ルーチン、(2)これらのパラメータに基づいて最適なベースアームのサブセットを選択するためのスーパーアーム選択ポリシーの2つの重要なサブルーチンが関係している。 最先端のアルゴリズムは、非有界な計算力を持つスーパーアーム選択のための正確なオラクルへのアクセスを前提としている。 それぞれの場合において、このオラクルはスコア関数の一覧を評価し、その数は、腕の数とともに、直線的に、指数的に増加する。 これは、多数の武器の体制において禁止される可能性がある。 本稿では,完全オラクルに代わる新しい現実的な代替案を紹介する。 このアルゴリズムは、スーパーアームの選択にグループテストとパラメータ推定に量子化されたトンプソンサンプリングを組み合わせたものである。 報奨関数に対する一般的な分離性仮定の下では,提案アルゴリズムは,正解法を用いる最先端アルゴリズムと同じ後悔順序を達成しつつ,ベースアーム数で対数となるスーパーアーム選択オラクルの複雑さを低減させる。 これは、少なくともオラクルベースのアプローチと比較して、複雑さが指数関数的に減少することを意味する。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• GBOSE: Generalized Bandit Orthogonalized Semiparametric Estimation [3.441021278275805]
  そこで本稿では,半パラメトリック報酬モデルを用いた新たなアルゴリズムを提案する。 我々の研究は、同じアクションフィルタリング法に基づいて構築されたアルゴリズムを提案することによって、同様の報酬モデルを用いて、最先端の複雑さの別の代表的アルゴリズムの範囲を広げる。 本研究は,2本以上の腕を持つ症例に対して,既知の半パラメトリックバンディットアルゴリズムから,これらの手法の優位性を確認するためのシミュレーション結果と,その上界の複雑さを導出したものである。
  論文  参考訳（メタデータ） (2023-01-20T19:39:10Z)
• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。 逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
  論文  参考訳（メタデータ） (2022-07-22T15:54:53Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)

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

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