論文の概要: Simulation Based Algorithms for Markov Decision Processes and
Multi-Action Restless Bandits
- arxiv url: http://arxiv.org/abs/2007.12933v1
- Date: Sat, 25 Jul 2020 13:50:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 01:26:30.390500
- Title: Simulation Based Algorithms for Markov Decision Processes and
Multi-Action Restless Bandits
- Title（参考訳）: マルコフ決定過程とマルチアクションレスバンドのシミュレーションに基づくアルゴリズム
- Authors: Rahul Meshram and Kesav Kaza
- Abstract要約: 我々は,多次元状態空間と多動作バンドイットモデルを備えたレスレスマルチアームバンドイット(RMAB)を考える。
まず、標準的なインデックス可能なRMAB(2アクションモデル)を分析し、インデックスベースのポリシーアプローチについて議論する。
モンテカルロロールアウトポリシを用いた近似インデックスアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider multi-dimensional Markov decision processes and formulate a long
term discounted reward optimization problem. Two simulation based
algorithms---Monte Carlo rollout policy and parallel rollout policy are
studied, and various properties for these policies are discussed. We next
consider a restless multi-armed bandit (RMAB) with multi-dimensional state
space and multi-actions bandit model. A standard RMAB consists of two actions
for each arms whereas in multi-actions RMAB, there are more that two actions
for each arms. A popular approach for RMAB is Whittle index based heuristic
policy. Indexability is an important requirement to use index based policy.
Based on this, an RMAB is classified into indexable or non-indexable bandits.
Our interest is in the study of Monte-Carlo rollout policy for both indexable
and non-indexable restless bandits. We first analyze a standard indexable RMAB
(two-action model) and discuss an index based policy approach. We present
approximate index computation algorithm using Monte-Carlo rollout policy. This
algorithm's convergence is shown using two-timescale stochastic approximation
scheme. Later, we analyze multi-actions indexable RMAB, and discuss the index
based policy approach. We also study non-indexable RMAB for both standard and
multi-actions bandits using Monte-Carlo rollout policy.
- Abstract（参考訳）: 我々は,多次元マルコフ決定過程を検討し,長期割引報酬最適化問題を定式化する。
シミュレーションに基づく2つのアルゴリズム-Monte Carloのロールアウトポリシーと並列ロールアウトポリシーについて検討し、これらのポリシーの様々な特性について論じる。
次に、多次元状態空間と多動作帯域モデルを備えたレスレスマルチアームバンド(RMAB)を考える。
標準的なRMABは各腕に対して2つのアクションからなるが、RMABでは各腕に対して2つのアクションがある。
RMABの一般的なアプローチはWhittle Indexベースのヒューリスティックポリシーである。
インデックスビリティは、インデックスベースのポリシーを使用するための重要な要件である。
これに基づいてRMABはインデクサブルまたは非インデクサブルバンディットに分類される。
私たちの関心は、インデックス付きおよび非インデックス型のrestless banditに対するモンテカルロロールアウトポリシーの研究にあります。
まず、標準のインデックス可能なrmab(two-action model)を分析し、インデックスベースのポリシーアプローチについて論じる。
モンテカルロロールアウトポリシを用いた近似インデックス計算アルゴリズムを提案する。
このアルゴリズムの収束は、2時間スケール確率近似スキームを用いて示される。
その後、インデクサブルRMABの分析を行い、インデクサブルポリシーのアプローチについて議論する。
また,モンテカルロのロールアウトポリシを用いて,標準およびマルチアクションバンディットの非インデクサブルRMABについても検討した。
関連論文リスト
- 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) - Global Rewards in Restless Multi-Armed Bandits [37.918982196934216]
レストレス・マルチアーム・バンディット(RMAB)はマルチアーム・バンディットを拡張し、腕を引っ張って将来の状態に影響を及ぼす。
RMABの成功にもかかわらず、重要な制限の前提は、報酬を武器の合計に分離できることである。
我々は、RMABのグローバル非分離報酬への一般化である、グローバル報酬(RMAB-G)を用いたレスレスマルチアームバンディットを提案する。
論文 参考訳（メタデータ） (2024-06-02T13:13:46Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Local Optimization Achieves Global Optimality in Multi-Agent
Reinforcement Learning [139.53668999720605]
本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。
マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
論文 参考訳（メタデータ） (2023-05-08T16:20:03Z) - Indexability of Finite State Restless Multi-Armed Bandit and Rollout
Policy [5.64327489637232]
有限状態定常多武装バンディット問題を考える。
レスレス・バンディットに対する古典的なアプローチは、Whittle Index Policyである。
本稿では,単一武装バンディットモデルの指標基準を検証するための代替手法を提案する。
論文 参考訳（メタデータ） (2023-04-30T06:53:44Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳（メタデータ） (2022-05-28T04:05:20Z) - Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits [8.136957953239254]
本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。
各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
論文 参考訳（メタデータ） (2021-09-20T21:40:12Z) - Q-Learning Lagrange Policies for Multi-Action Restless Bandits [35.022322303796216]
RMAB(Multi-action restless multi-armed bandits)は、N$独立プロセスを管理する制約付きリソース割り当てのための強力なフレームワークである。
我々は,ラグランジアン緩和とQラーニングを組み合わせて,Multi-action RMABをオンラインで学習するための最初のアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-22T19:20:09Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。