論文の概要: Learning to Detect an Odd Restless Markov Arm with a Trembling Hand

• arxiv url: http://arxiv.org/abs/2105.03603v1
• Date: Sat, 8 May 2021 05:53:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-13 10:18:13.649241
• Title: Learning to Detect an Odd Restless Markov Arm with a Trembling Hand
• Title（参考訳）: トリミングハンドで無休のマルコフアームを検知する学習
• Authors: P. N. Karthik and Rajesh Sundaresan
• Abstract要約: 異常とは、片方の腕の遷移確率行列が、片方の非オードアームの共通TPMと異なることを意味する。 我々は,確実性同値原理に基づく政策を考案し,連続選択仮定とtpms上の一定の規則性仮定の下で,その政策が任意に下限を満たしていることを示す。 我々の実現可能性分析は、可算状態制御マルコフ過程の文脈における識別可能性問題の解法に基づいている。
• 参考スコア（独自算出の注目度）: 12.467685221424032
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the problem of finding an anomalous arm in a multi-armed bandit when (a) each arm is a finite-state Markov process, and (b) the arms are restless. Here, anomaly means that the transition probability matrix (TPM) of one of the arms (the odd arm) is different from the common TPM of each of the non-odd arms. The TPMs are unknown to a decision entity that wishes to find the index of the odd arm as quickly as possible, subject to an upper bound on the error probability. We derive a problem instance specific asymptotic lower bound on the expected time required to find the odd arm index, where the asymptotics is as the error probability vanishes. Further, we devise a policy based on the principle of certainty equivalence, and demonstrate that under a continuous selection assumption and a certain regularity assumption on the TPMs, the policy achieves the lower bound arbitrarily closely. Thus, while the lower bound is shown for all problem instances, the upper bound is shown only for those problem instances satisfying the regularity assumption. Our achievability analysis is based on resolving the identifiability problem in the context of a certain countable-state controlled Markov process.
• Abstract（参考訳）: 本稿では, (a) 各アームが有限状態マルコフ過程であり, (b) アームがレストである場合, 多腕のバンディットにおいて異常なアームを見つける問題について検討する。 ここでの異常とは、一方の腕(奇腕)の遷移確率行列(TPM)が他方の腕の共通のTPMとは異なることを意味する。 TPMは、エラー確率の上限を条件として、奇腕の指数をできるだけ早く見つけようとする決定エンティティには未知である。 我々は、異常なアーム指数を見つけるのに必要な期待時間に基づいて、問題のインスタンス固有の漸近的下限を導出する。 さらに, 確実性同値原理に基づく政策を考案し, 連続選択仮定とtpms上の一定の規則性仮定の下で, 政策が任意に下限を満たしていることを示す。 したがって、下限はすべての問題インスタンスに対して示されるが、上限は正規性仮定を満たす問題インスタンスに対してのみ示される。 我々の実現可能性分析は、可算状態制御マルコフ過程の文脈における識別可能性問題の解法に基づいている。

関連論文リスト

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• 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)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• From Finite to Countable-Armed Bandits [8.099977107670918]
  有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。 武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。 我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-22T13:09:50Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Detecting an Odd Restless Markov Arm with a Trembling Hand [18.122816058828906]
  我々は、各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットを考える。 片方のアーム(奇腕)の遷移確率行列は、他のアームの共通の遷移確率行列とは異なる。 意思決定者は、決定誤差の確率を小さく保ちながら、奇異腕をできるだけ早く特定したい。
  論文  参考訳（メタデータ） (2020-05-13T11:27:14Z)

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

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