論文の概要: Learning in Restless Bandits under Exogenous Global Markov Process
- arxiv url: http://arxiv.org/abs/2112.09484v1
- Date: Fri, 17 Dec 2021 12:47:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-20 15:46:50.192749
- Title: Learning in Restless Bandits under Exogenous Global Markov Process
- Title(参考訳): 外因性グローバルマルコフ過程におけるレストレスバンディットの学習
- Authors: Tomer Gafni, Michal Yemini, Kobi Cohen
- Abstract要約: レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,後悔を最小限に抑えるために,外因性マルコフ過程(LEMP)に基づく学習法を開発した。
- 参考スコア(独自算出の注目度): 13.836565669337057
- 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. Motivated by recent studies on related RMAB
settings, the regret is 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. The objective is to develop an
arm-selection policy that minimizes the regret. To that end, we develop the
Learning under Exogenous Markov Process (LEMP) algorithm. We analyze LEMP
theoretically and establish a finite-sample bound on the regret. We show that
LEMP achieves a logarithmic regret order with time. We further analyze LEMP
numerically and present simulation results that support the theoretical
findings and demonstrate that LEMP significantly outperforms alternative
algorithms.
- Abstract(参考訳): 我々は、未知の腕力学によるレスレスマルチアームバンディット(RMAB)問題の拡張を検討し、未知の外因性グローバルマルコフ過程が各腕の報酬分布を制御している。
それぞれの世界状態の下では、各腕の報酬過程は未知のマルコフ則に従って進化し、異なる腕の間では識別されない。
毎回、プレイヤーはn$のアームからアームを選択し、有限の報酬状態からランダムな報酬を受け取る。
腕は落ち着かない、つまり、プレイヤーのアクションに関係なく局所的な状態が進化する。
RMAB設定に関する最近の研究によって動機づけられた後悔は、問題のダイナミクスを知っているプレイヤーに対する報酬損失として定義され、期待される即時値を最大化するアームに対して$t$で演奏される。
目的は、後悔を最小限に抑えるアーム選択政策を開発することである。
そこで我々は,Learning under Exogenous Markov Process (LEMP)アルゴリズムを開発した。
我々はLEMPを理論的に解析し、後悔に縛られる有限サンプルを確立する。
LEMPは時間とともに対数的後悔の順序を達成できることを示す。
さらに、LEMPを数値解析し、理論的な結果を支持するシミュレーション結果を提示し、LEMPが代替アルゴリズムを著しく上回っていることを示す。
関連論文リスト
- Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints [17.403031677689427]
我々は「長期公正制約」を持つ新しいRMABモデルを導入する。
オンラインRMAB-F設定では、各腕に関連する基礎となるMDPがDMに未知である。
Fair-UCRLは、報酬の後悔と公正性違反の両面において、確率的サブリニア境界を保証することを証明している。
論文 参考訳(メタデータ) (2023-12-16T03:35:56Z) - Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳(メタデータ) (2023-11-27T09:19:01Z) - Optimal Best Arm Identification with Fixed Confidence in Restless
Bandits [72.86567379444153]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳(メタデータ) (2023-10-20T10:04:05Z) - 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) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。
本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
論文 参考訳(メタデータ) (2021-12-08T02:20:18Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳(メタデータ) (2021-03-03T23:08:59Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z) - Detecting an Odd Restless Markov Arm with a Trembling Hand [18.122816058828906]
我々は、各アームが有限状態空間上で進化するマルコフ過程である多腕バンディットを考える。
片方のアーム(奇腕)の遷移確率行列は、他のアームの共通の遷移確率行列とは異なる。
意思決定者は、決定誤差の確率を小さく保ちながら、奇異腕をできるだけ早く特定したい。
論文 参考訳(メタデータ) (2020-05-13T11:27:14Z) - Ballooning Multi-Armed Bandits [12.205797997133397]
バルーン式マルチアーマッドバンド(BL-MAB)について紹介する。
BL-MABでは、利用可能なアームのセットは時間とともに成長する。
ベストアームが任意のタイミングで到着する確率が等しく高い場合、サブリニアな後悔は達成できないことを示す。
論文 参考訳(メタデータ) (2020-01-24T04:35:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。