論文の概要: Best Arm Identification in Restless Markov Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2203.15236v1
• Date: Tue, 29 Mar 2022 04:58:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-31 06:09:24.453004
• Title: Best Arm Identification in Restless Markov Multi-Armed Bandits
• Title（参考訳）: レスレスマルコフ多関節バンドにおけるベストアーム識別
• Authors: P. N. Karthik, Kota Srinivas Reddy, Vincent Y. F. Tan
• Abstract要約: マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
• 参考スコア（独自算出の注目度）: 85.55466536537293
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of identifying the best arm in a multi-armed bandit environment when each arm is a time-homogeneous and ergodic discrete-time Markov process on a common, finite state space. The state evolution on each arm is governed by the arm's transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. The decision entity selects one arm at a time sequentially, and all the unselected arms continue to undergo state evolution ({\em restless} arms). For this problem, we derive the first-known problem instance-dependent asymptotic lower bound on the growth rate of the expected time required to find the index of the best arm, where the asymptotics is as the error probability vanishes. Further, we propose a sequential policy that, for an input parameter $R$, forcibly selects an arm that has not been selected for $R$ consecutive time instants. We show that this policy achieves an upper bound that depends on $R$ and is monotonically non-increasing as $R\to\infty$. The question of whether, in general, the limiting value of the upper bound as $R\to\infty$ matches with the lower bound, remains open. We identify a special case in which the upper and the lower bounds match. Prior works on best arm identification have dealt with (a) independent and identically distributed observations from the arms, and (b) rested Markov arms, whereas our work deals with the more difficult setting of restless Markov arms.
• Abstract（参考訳）: 各アームが共通な有限状態空間上の時間均質かつエルゴード離散時間マルコフ過程である場合、マルチアームバンディット環境で最適なアームを識別する問題を考察する。 各腕の状態進化は、腕の遷移確率行列(TPM)によって制御される。 アーム tpm のセットを知っているが、tpm の腕への正確なマッピングではない決定エンティティは、エラー確率の上限を条件として、できるだけ早く最良アームの指標を見つけることを望んでいる。 決定機関は、連続して1つの腕を選択し、選択されていないすべての腕は、状態の進化を継続する。 そこで本研究では, 最良アームの指数を求めるのに必要な所要時間の増加率について, 第一の既知の問題インスタンス依存漸近下限を導出する。 さらに,入力パラメータ $r$ に対して,$r$ の連続時間インスタントに対して選択されていない arm を強制的に選択するシーケンシャルポリシーを提案する。 このポリシーは、$R$に依存する上限に達し、$R\to\infty$として単調に増加しないことを示す。 一般に、上界の制限値である$R\to\infty$が下界と一致するかどうかという問題は開のままである。 上界と下界が一致する特別な場合を特定する。 腕の識別に関する先行研究が対処した a) 腕から独立かつ同一に分布した観察,及び b) マルコフの腕を休ませる一方、我々の仕事はマルコフの腕を休めるのがより難しい。

関連論文リスト

• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• 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)
• 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)

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

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