論文の概要: Detecting an Odd Restless Markov Arm with a Trembling Hand
- arxiv url: http://arxiv.org/abs/2005.06255v3
- Date: Thu, 31 Dec 2020 10:43:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 13:35:36.080495
- Title: Detecting an Odd Restless Markov Arm with a Trembling Hand
- Title（参考訳）: 震えハンドによる不規則なレストレス・マルコフアームの検出
- Authors: P. N. Karthik and Rajesh Sundaresan
- Abstract要約: 我々は、各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットを考える。
片方のアーム(奇腕)の遷移確率行列は、他のアームの共通の遷移確率行列とは異なる。
意思決定者は、決定誤差の確率を小さく保ちながら、奇異腕をできるだけ早く特定したい。
- 参考スコア（独自算出の注目度）: 18.122816058828906
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a multi-armed bandit in which each arm is a Markov
process evolving on a finite state space. The state space is common across the
arms, and the arms are independent of each other. The transition probability
matrix of one of the arms (the odd arm) is different from the common transition
probability matrix of all the other arms. A decision maker, who knows these
transition probability matrices, wishes to identify the odd arm as quickly as
possible, while keeping the probability of decision error small. To do so, the
decision maker collects observations from the arms by pulling the arms in a
sequential manner, one at each discrete time instant. However, the decision
maker has a trembling hand, and the arm that is actually pulled at any given
time differs, with a small probability, from the one he intended to pull. The
observation at any given time is the arm that is actually pulled and its
current state. The Markov processes of the unobserved arms continue to evolve.
This makes the arms restless.
For the above setting, we derive the first known asymptotic lower bound on
the expected time required to identify the odd arm, where the asymptotics is of
vanishing error probability. The continued evolution of each arm adds a new
dimension to the problem, leading to a family of Markov decision problems
(MDPs) on a countable state space. We then stitch together certain
parameterised solutions to these MDPs and obtain a sequence of strategies whose
expected times to identify the odd arm come arbitrarily close to the lower
bound in the regime of vanishing error probability. Prior works dealt with
independent and identically distributed (across time) arms and rested Markov
arms, whereas our work deals with restless Markov arms.
- Abstract（参考訳）: 本稿では,各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットについて考察する。
州の空間は両腕に共通しており、両腕は互いに独立している。
1つのアーム(奇腕)の遷移確率行列は、他の全てのアームの共通遷移確率行列とは異なる。
この遷移確率行列を知っている意思決定者は、決定誤差の確率を小さく保ちながら、奇腕をできるだけ早く識別したいと考えている。
そのため、意思決定者は、各離散時間に1つずつ、連続的に腕を引いて腕から観察を収集する。
しかし、意思決定者は震える手を持ち、実際に任意のタイミングに引っ張られる腕は、彼が引こうとしていた腕と小さな確率で異なる。
いつでも観察されるのは、実際に引っ張られる腕とその現在の状態である。
観測されていない腕のマルコフ過程は進化を続けている。
これは腕を休ませる。
上記の設定では、奇腕を特定するのに必要な期待時間に基づいて、最初の既知の漸近的下界を導出する。
各アームの継続的な進化は問題に新たな次元を加え、可算状態空間上のマルコフ決定問題(mdps)の一群へと導かれる。
次に,これらのmdpに対するパラメータ化解を縫い合わせることで,誤り確率が消失する状態において,奇腕を識別するための予測時間が任意に下界に近くなる一連の戦略を得る。
それまでの作業では、独立して均等に分散した(時を超えて)武器を扱い、マルコフの腕を休ませていました。
関連論文リスト
- 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) - 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) - Restless Multi-Armed Bandits under Exogenous Global Markov Process [20.58296570065978]
レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,対数的後悔順序を時間とともに達成するLearning under Exogenous Markov Process (LEMP)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-02-28T10:29:42Z) - Learning in Restless Bandits under Exogenous Global Markov Process [13.836565669337057]
レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,後悔を最小限に抑えるために,外因性マルコフ過程(LEMP)に基づく学習法を開発した。
論文 参考訳（メタデータ） (2021-12-17T12:47:30Z) - Learning to Detect an Odd Restless Markov Arm with a Trembling Hand [12.467685221424032]
異常とは、片方の腕の遷移確率行列が、片方の非オードアームの共通TPMと異なることを意味する。
我々は,確実性同値原理に基づく政策を考案し,連続選択仮定とtpms上の一定の規則性仮定の下で,その政策が任意に下限を満たしていることを示す。
我々の実現可能性分析は、可算状態制御マルコフ過程の文脈における識別可能性問題の解法に基づいている。
論文 参考訳（メタデータ） (2021-05-08T05:53:12Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳（メタデータ） (2020-12-07T08:23:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。