論文の概要: Optimal Best Arm Identification with Fixed Confidence in Restless
Bandits
- arxiv url: http://arxiv.org/abs/2310.13393v1
- Date: Fri, 20 Oct 2023 10:04:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-23 23:26:45.157694
- 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要約: 本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
- 参考スコア（独自算出の注目度）: 72.86567379444153
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。