論文の概要: Restless Multi-Armed Bandits under Exogenous Global Markov Process
- arxiv url: http://arxiv.org/abs/2202.13665v1
- Date: Mon, 28 Feb 2022 10:29:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-01 18:27:42.692373
- Title: Restless Multi-Armed Bandits under Exogenous Global Markov Process
- Title（参考訳）: 外因性グローバルマルコフ過程におけるレストレスマルチアームバンディット
- Authors: Tomer Gafni, Michal Yemini, Kobi Cohen
- Abstract要約: レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,対数的後悔順序を時間とともに達成するLearning under Exogenous Markov Process (LEMP)アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 20.58296570065978
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider an extension to the restless multi-armed bandit (RMAB) problem
with unknown arm dynamics, where an unknown exogenous global Markov process
governs the rewards distribution of each arm. Under each global state, the
rewards process of each arm evolves according to an unknown Markovian rule,
which is non-identical among different arms. At each time, a player chooses an
arm out of N arms to play, and receives a random reward from a finite set of
reward states. The arms are restless, that is, their local state evolves
regardless of the player's actions. The objective is an arm-selection policy
that minimizes the regret, defined as the reward loss with respect to a player
that knows the dynamics of the problem, and plays at each time t the arm that
maximizes the expected immediate value. We develop the Learning under Exogenous
Markov Process (LEMP) algorithm, that achieves a logarithmic regret order with
time, and a finite-sample bound on the regret is established. Simulation
results support the theoretical study and demonstrate strong performances of
LEMP.
- Abstract（参考訳）: 我々は、未知の腕力学によるレスレスマルチアームバンディット(RMAB)問題の拡張を検討し、未知の外因性グローバルマルコフ過程が各腕の報酬分布を制御している。
それぞれの世界状態の下では、各腕の報酬過程は未知のマルコフ則に従って進化し、異なる腕の間では識別されない。
毎回、プレイヤーはn個のアームのうちの1つのアームを選択し、有限の報酬状態からランダムな報酬を受け取る。
腕は落ち着かない、つまり、プレイヤーのアクションに関係なく局所的な状態が進化する。
目的は、問題のダイナミクスを知っているプレイヤーに対して報酬損失として定義された後悔を最小限に抑え、期待される即時値を最大化するアームtでプレーするアーム選択ポリシーである。
我々は,時間とともに対数的後悔順序を達成する外部帰属マルコフ過程(lemp)アルゴリズムによる学習を開発し,その後悔に束縛された有限サンプルが確立される。
シミュレーション結果は理論研究を支援し,lempの強力な性能を示す。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-08-20T13:57:00Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳（メタデータ） (2023-10-20T10:04:05Z) - Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits [6.732901486505047]
マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用を動機とした、ますます関連する意思決定問題である。
本稿では、前述のモデリング問題に対処することを目的とした、テキストマルチプレーヤのマルチアームウォーキングバンディットモデルを提案する。
論文 参考訳（メタデータ） (2022-12-12T23:26:02Z) - Information-Gathering in Latent Bandits [79.6953033727455]
本稿では,潜伏バンドにおける情報収集手法を提案する。
我々は、各州に対するエージェントの信念から、最高の腕を選ぶことは、より高い後悔を引き起こすことを示した。
また,腕を慎重に選択することで,状態分布の推定精度が向上することを示した。
論文 参考訳（メタデータ） (2022-07-08T01:15:12Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Learning in Restless Bandits under Exogenous Global Markov Process [13.836565669337057]
レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,後悔を最小限に抑えるために,外因性マルコフ過程(LEMP)に基づく学習法を開発した。
論文 参考訳（メタデータ） (2021-12-17T12:47:30Z) - Detecting an Odd Restless Markov Arm with a Trembling Hand [18.122816058828906]
我々は、各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットを考える。
片方のアーム(奇腕)の遷移確率行列は、他のアームの共通の遷移確率行列とは異なる。
意思決定者は、決定誤差の確率を小さく保ちながら、奇異腕をできるだけ早く特定したい。
論文 参考訳（メタデータ） (2020-05-13T11:27:14Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。