論文の概要: Multi-Armed Bandits with Dependent Arms

• arxiv url: http://arxiv.org/abs/2010.09478v2
• Date: Fri, 23 Oct 2020 21:06:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-08 01:03:05.342496
• Title: Multi-Armed Bandits with Dependent Arms
• Title（参考訳）: 従属腕を持つ多関節バンド
• Authors: Rahul Singh, Fang Liu, Yin Sun and Ness Shroff
• Abstract要約: 我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。 複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。 UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
• 参考スコア（独自算出の注目度）: 18.81667618369821
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a variant of the classical multi-armed bandit problem (MABP) which we call as Multi-Armed Bandits with dependent arms. More specifically, multiple arms are grouped together to form a cluster, and the reward distributions of arms belonging to the same cluster are known functions of an unknown parameter that is a characteristic of the cluster. Thus, pulling an arm $i$ not only reveals information about its own reward distribution, but also about all those arms that share the same cluster with arm $i$. This "correlation" amongst the arms complicates the exploration-exploitation trade-off that is encountered in the MABP because the observation dependencies allow us to test simultaneously multiple hypotheses regarding the optimality of an arm. We develop learning algorithms based on the UCB principle which utilize these additional side observations appropriately while performing exploration-exploitation trade-off. We show that the regret of our algorithms grows as $O(K\log T)$, where $K$ is the number of clusters. In contrast, for an algorithm such as the vanilla UCB that is optimal for the classical MABP and does not utilize these dependencies, the regret scales as $O(M\log T)$ where $M$ is the number of arms.
• Abstract（参考訳）: 我々は,マルチアームバンディット (multi-armed bandit) 問題 (mabp) の変種について検討した。 より具体的には、複数のアームをグループ化してクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。 従って、arm $i$を引けば、自身の報酬分布に関する情報だけでなく、arm $i$で同じクラスタを共有するすべてのアームに関する情報も明らかになる。 このアーム間の「相関」は、観測依存性によってアームの最適性に関する複数の仮説を同時にテストできるため、mabpで遭遇する探索・爆発のトレードオフを複雑にする。 探索-探索トレードオフを行いながら,これらの追加の側面観測を適切に活用する,ucb原理に基づく学習アルゴリズムを開発した。 我々のアルゴリズムの後悔は$O(K\log T)$として増大し、そこでは$K$はクラスタの数である。 対照的に、古典的なmabpに最適でこれらの依存関係を使用しないvanilla ucbのようなアルゴリズムでは、後悔は$o(m\log t)$となり、ここで$m$は腕の数である。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
  遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。 我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。 問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
  論文  参考訳（メタデータ） (2023-01-18T00:53:46Z)
• Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
  無限に多くの腕からなる群が多数存在するバンド問題。 本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。 インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
  論文  参考訳（メタデータ） (2022-10-04T00:46:49Z)
• 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)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。 C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
  論文  参考訳（メタデータ） (2021-09-10T15:41:07Z)
• 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)

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

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