論文の概要: Optimal Best Arm Identification with Fixed Confidence in Restless Bandits

• arxiv url: http://arxiv.org/abs/2310.13393v2
• Date: Sun, 23 Jun 2024 06:58:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-26 04:48:52.701320
• Title: Optimal Best Arm Identification with Fixed Confidence in Restless Bandits
• Title（参考訳）: レスレスバンドの信頼度を固定した最適な腕同定法
• Authors: P. N. Karthik, Vincent Y. F. Tan, Arpan Mukherjee, Ali Tajer,
• Abstract要約: 本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
• 参考スコア（独自算出の注目度）: 66.700654953613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space. The state transitions in each arm are captured by an ergodic transition probability matrix (TPM) that is a member of a single-parameter exponential family of TPMs. The real-valued parameters of the arm TPMs are unknown and belong to a given space. Given a function $f$ defined on the common state space of the arms, the goal is to identify the best arm -- the arm with the largest average value of $f$ evaluated under the arm's stationary distribution -- with the fewest number of samples, subject to an upper bound on the decision's error probability (i.e., the fixed-confidence regime). A lower bound on the growth rate of the expected stopping time is established in the asymptote of a vanishing error probability. Furthermore, a policy for best arm identification is proposed, and its expected stopping time is proved to have an asymptotic growth rate that matches the lower bound. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds. It is shown that under every policy, the state-action visitation proportions satisfy a specific approximate flow conservation constraint and that these proportions match the optimal proportions dictated by the lower bound under any asymptotically optimal policy. The prior studies on best arm identification in restless bandits focus on independent observations from the arms, rested Markov arms, and restless Markov arms with known arm TPMs. In contrast, this work is the first to study best arm identification in restless bandits with unknown arm TPMs.
• Abstract（参考訳）: 本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 各アームの状態遷移は、TPMの1パラメータ指数族に属するエルゴード遷移確率行列(TPM)によって捕捉される。 腕のTPMの実際の値パラメータは未知であり、与えられた空間に属する。 腕の共通状態空間上で定義される関数 $f$ が与えられたとき、ゴールは、腕の固定分布の下で評価される最も平均値$f$ の腕を、決定の誤差確率(すなわち、固定信頼状態)の上限が最少のサンプル数で識別することである。 消滅する誤差確率の漸近に、期待停止時間の成長速度に対する低い境界を確立する。 さらに、ベストアーム識別のためのポリシーを提案し、その期待される停止時間は、下限と一致する漸近的な成長速度を持つことを証明した。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。 すべての政策において、状態-行動の訪問比率は特定の近似フロー保存制約を満たすことが示され、これらの比率は漸近的に最適な政策の下で下界によって決定される最適比率と一致することが示されている。 休眠帯における最高の腕の識別に関する以前の研究は、腕からの独立した観察、休息したマルコフの腕、そして既知の腕のTPMを持つレストレスのマルコフの腕に焦点を当てていた。 対照的に、この研究は、未知の腕TPMを持つレストレス・バンディットにおいて、最も優れた腕の識別を研究した最初のものである。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget [10.470114319701576]
  本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。 分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。 GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
  論文  参考訳（メタデータ） (2023-10-30T17:52:46Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Covariance Adaptive Best Arm Identification [0.0]
  ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。 武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。 この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
  論文  参考訳（メタデータ） (2023-06-05T06:57:09Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• 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)
• Learning to Detect an Odd Restless Markov Arm with a Trembling Hand [12.467685221424032]
  異常とは、片方の腕の遷移確率行列が、片方の非オードアームの共通TPMと異なることを意味する。 我々は,確実性同値原理に基づく政策を考案し,連続選択仮定とtpms上の一定の規則性仮定の下で,その政策が任意に下限を満たしていることを示す。 我々の実現可能性分析は、可算状態制御マルコフ過程の文脈における識別可能性問題の解法に基づいている。
  論文  参考訳（メタデータ） (2021-05-08T05:53:12Z)
• Detecting an Odd Restless Markov Arm with a Trembling Hand [18.122816058828906]
  我々は、各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットを考える。 片方のアーム(奇腕)の遷移確率行列は、他のアームの共通の遷移確率行列とは異なる。 意思決定者は、決定誤差の確率を小さく保ちながら、奇異腕をできるだけ早く特定したい。
  論文  参考訳（メタデータ） (2020-05-13T11:27:14Z)

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

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