論文の概要: Max-Quantile Grouped Infinite-Arm Bandits
- arxiv url: http://arxiv.org/abs/2210.01295v1
- Date: Tue, 4 Oct 2022 00:46:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 13:48:24.631724
- Title: Max-Quantile Grouped Infinite-Arm Bandits
- Title（参考訳）: Max-Quantile Grouped Infinite-Arm Bandits
- Authors: Ivan Lau, Yan Hao Ling, Mayank Shrivastava, Jonathan Scarlett
- Abstract要約: 無限に多くの腕からなる群が多数存在するバンド問題。
本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。
インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
- 参考スコア（独自算出の注目度）: 39.7239093424124
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a bandit problem in which there are a number of
groups each consisting of infinitely many arms. Whenever a new arm is requested
from a given group, its mean reward is drawn from an unknown reservoir
distribution (different for each group), and the uncertainty in the arm's mean
reward can only be reduced via subsequent pulls of the arm. The goal is to
identify the infinite-arm group whose reservoir distribution has the highest
$(1-\alpha)$-quantile (e.g., median if $\alpha = \frac{1}{2}$), using as few
total arm pulls as possible. We introduce a two-step algorithm that first
requests a fixed number of arms from each group and then runs a finite-arm
grouped max-quantile bandit algorithm. We characterize both the
instance-dependent and worst-case regret, and provide a matching lower bound
for the latter, while discussing various strengths, weaknesses, algorithmic
improvements, and potential lower bounds associated with our instance-dependent
upper bounds.
- Abstract（参考訳）: 本稿では,無限個の腕からなる群が多数存在するというバンドイット問題を考える。
与えられたグループから新しいアームが要求されると、その平均報酬は未知の貯水池分布(各グループ毎に異なる)から引き出され、アームの平均報酬の不確実性は、その後のアームのプルによってのみ低減される。
目的は、貯水池分布が最高$(1-\alpha)$-quantile(例えば、中央値が$\alpha = \frac{1}{2}$)を持つ無限腕群を、できるだけ少ない総アームプルを用いて特定することである。
まず,各群から固定数のアームをリクエストし,次に有限個のアーム群を持つmax-quantile banditアルゴリズムを実行する2段階アルゴリズムを導入する。
我々は、インスタンス依存と最悪ケースの両方の後悔を特徴づけ、インスタンス依存の上界に関連する様々な強み、弱点、アルゴリズム的改善、潜在的下界を議論しながら、後者に一致する下界を提供する。
関連論文リスト
- Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。
逐次除去に基づく指数時間ステップでのみ通信を行う新しいアルゴリズム sc FedElim を提案する。
論文 参考訳（メタデータ） (2022-08-19T08:37:09Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Contextual Combinatorial Multi-output GP Bandits with Group Constraints [11.317136648551537]
連合型多武装バンディット問題では、クライアントを保護するための最小限のプライバシー要件を満たしながら、世界的報酬を最大化することが主な目標である。
我々は、グループやアクションセットの変更によるコンテキスト的バンディットの設定を検討し、そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、スーパーアームの報酬を最大化し、ベースアームが選択されたグループの報酬の制約を満たす。
次に、累積スーパーアーム報酬の最大化と充足のバランスをとる、Thresholded Combinatored upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-29T18:39:09Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - 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) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Quantile Bandits for Best Arms Identification [10.294977861990203]
多腕バンディットにおける最適な腕識別タスクの変種について検討する。
リスクと逆の意思決定の問題によって動機づけられた当社の目標は、固定予算内で最高の$tau$-quantileの値を持つ、$m$の武器のセットを特定することです。
論文 参考訳（メタデータ） (2020-10-22T09:58:54Z) - Multi-Armed Bandits with Dependent Arms [18.81667618369821]
我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。
複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。
UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
論文 参考訳（メタデータ） (2020-10-13T14:00:19Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。