論文の概要: Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits
- arxiv url: http://arxiv.org/abs/2109.09855v1
- Date: Mon, 20 Sep 2021 21:40:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-22 14:30:20.982718
- Title: Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits
- Title(参考訳): 有限ホリゾンレストレストレスマルチアームマルチアクションバンディットの強化学習
- Authors: Guojun Xiong, Jian Li, Rahul Singh
- Abstract要約: 本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。
各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
- 参考スコア(独自算出の注目度): 8.136957953239254
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a finite-horizon restless multi-armed bandit problem with multiple
actions, dubbed R(MA)^2B. The state of each arm evolves according to a
controlled Markov decision process (MDP), and the reward of pulling an arm
depends on both the current state of the corresponding MDP and the action
taken. The goal is to sequentially choose actions for arms so as to maximize
the expected value of the cumulative rewards collected. Since finding the
optimal policy is typically intractable, we propose a computationally appealing
index policy which we call Occupancy-Measured-Reward Index Policy. Our policy
is well-defined even if the underlying MDPs are not indexable. We prove that it
is asymptotically optimal when the activation budget and number of arms are
scaled up, while keeping their ratio as a constant. For the case when the
system parameters are unknown, we develop a learning algorithm. Our learning
algorithm uses the principle of optimism in the face of uncertainty and further
uses a generative model in order to fully exploit the structure of
Occupancy-Measured-Reward Index Policy. We call it the R(MA)^2B-UCB algorithm.
As compared with the existing algorithms, R(MA)^2B-UCB performs close to an
offline optimum policy, and also achieves a sub-linear regret with a low
computational complexity. Experimental results show that R(MA)^2B-UCB
outperforms the existing algorithms in both regret and run time.
- Abstract(参考訳): 我々は、R(MA)^2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題を研究する。
各腕の状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、腕を引く報酬は、対応するMDPの現在の状態と取られた動作の両方に依存する。
目標は、収集した累積報酬の期待値を最大化するために、武器のアクションを順次選択することである。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
私たちの政策は、基礎となるMDPがインデックス化できない場合でも明確に定義されています。
我々は、アクティベーション予算と腕の数を増加させながら、その比率を一定に保ちながら漸近的に最適であることを示す。
システムパラメータが未知の場合、学習アルゴリズムを開発する。
本学習アルゴリズムは,不確実性に直面した楽観主義の原理を用い,さらに生成モデルを用いて,占有度測定指標ポリシの構造を十分に活用する。
R(MA)^2B-UCBアルゴリズムと呼ぶ。
既存のアルゴリズムと比較して、R(MA)^2B-UCBはオフラインの最適ポリシーに近く、計算複雑性の低いサブ線形後悔を実現する。
実験の結果, R(MA)^2B-UCBは, 後悔と実行の両方で既存アルゴリズムよりも優れていた。
関連論文リスト
- GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits [16.054685587034836]
GINO-Qは、レスレスマルチアームバンディット(RMAB)の最適指標ポリシーを学習するために設計された3段階近似アルゴリズムである。
GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。
実験結果から, GINO-Q は非接種可能なRMABに対しても, ほぼ最適に学習できることが示唆された。
論文 参考訳(メタデータ) (2024-08-19T10:50:45Z) - Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs [9.58750210024265]
バンディットとマルコフ決定過程(MDP)に対する(確率的)ソフトマックスポリシー勾配(PG)法について検討する。
提案アルゴリズムは,技術結果と類似した理論的保証を提供するが,オラクルのような量の知識は必要としないことを示す。
マルチアームバンディット設定の場合,提案手法は明示的な探索や報奨ギャップの知識,報奨分布,ノイズを必要としない理論的なPGアルゴリズムを実現する。
論文 参考訳(メタデータ) (2024-05-21T18:12:39Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit [7.708904950194129]
動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
論文 参考訳(メタデータ) (2023-06-09T16:10:26Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits [30.532795983761314]
本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。
まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。
次に,平均場法に基づく代替計画アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-31T19:35:15Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-04T17:13:45Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳(メタデータ) (2022-08-17T18:49:53Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Robust Reinforcement Learning using Least Squares Policy Iteration with
Provable Performance Guarantees [3.8073142980733]
本稿では,ロバストマルコフ決定過程(RMDP)におけるモデルレス強化学習の課題について述べる。
本稿では、まず、ポリシー評価のための多段階オンラインモデルフリー学習アルゴリズムであるRobust Least Squares Policy Evaluationアルゴリズムを提案する。
次に,ロバスト・ラスト・スクエアズ・ポリシー・イテレーション (RLSPI) アルゴリズムを提案し,ロバスト・ラスト・スクエアズ・ポリシーを最適に学習する。
論文 参考訳(メタデータ) (2020-06-20T16:26:50Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。