論文の概要: Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy

• arxiv url: http://arxiv.org/abs/2305.00410v1
• Date: Sun, 30 Apr 2023 06:53:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 15:25:44.403136
• Title: Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy
• Title（参考訳）: 有限状態レストレストマルチアームバンディットのインデクシング可能性とロールアウトポリシー
• Authors: Vishesh Mittal, Rahul Meshram, Deepak Dev and Surya Prakash
• Abstract要約: 有限状態定常多武装バンディット問題を考える。 レスレス・バンディットに対する古典的なアプローチは、Whittle Index Policyである。 本稿では,単一武装バンディットモデルの指標基準を検証するための代替手法を提案する。
• 参考スコア（独自算出の注目度）: 5.64327489637232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider finite state restless multi-armed bandit problem. The decision maker can act on M bandits out of N bandits in each time step. The play of arm (active arm) yields state dependent rewards based on action and when the arm is not played, it also provides rewards based on the state and action. The objective of the decision maker is to maximize the infinite horizon discounted reward. The classical approach to restless bandits is Whittle index policy. In such policy, the M arms with highest indices are played at each time step. Here, one decouples the restless bandits problem by analyzing relaxed constrained restless bandits problem. Then by Lagrangian relaxation problem, one decouples restless bandits problem into N single-armed restless bandit problems. We analyze the single-armed restless bandit. In order to study the Whittle index policy, we show structural results on the single armed bandit model. We define indexability and show indexability in special cases. We propose an alternative approach to verify the indexable criteria for a single armed bandit model using value iteration algorithm. We demonstrate the performance of our algorithm with different examples. We provide insight on condition of indexability of restless bandits using different structural assumptions on transition probability and reward matrices. We also study online rollout policy and discuss the computation complexity of algorithm and compare that with complexity of index computation. Numerical examples illustrate that index policy and rollout policy performs better than myopic policy.
• Abstract（参考訳）: 有限状態定常多武装バンディット問題を考える。 意思決定者は、各タイムステップでNのバンドイットからMのバンドイットに作用することができる。 腕(アクティブアーム)の演奏は、動作に基づいて状態依存の報酬を与えるが、腕が演奏されていない場合は、状態と動作に基づいて報酬を与える。 決定者の目的は、無限の地平線割引報酬を最大化することである。 restless banditsに対する古典的なアプローチは、whitle index policyである。 このような政策では、最高指標のMアームが各ステップで演奏される。 ここで、リラックスした制約付きrestless bandits問題を分析して、restless bandits問題を分離する。 そして、ラグランジアン緩和問題により、1つのスリーレスバンディット問題をN個のスリーレスバンディット問題に分解する。 単腕レストレスバンディットの分析を行う。 ウィトル指数政策を研究するために,単一武装バンディットモデルを用いて構造的な結果を示す。 指数性を定義し、特別の場合において指数性を示す。 本稿では,値反復アルゴリズムを用いて,単一武装バンディットモデルの指標基準を検証するための代替手法を提案する。 我々は,このアルゴリズムの性能を実例で示す。 遷移確率と報酬行列の異なる構造的仮定を用いて,restless banditのインデクシング可能性の条件について考察する。 また、オンラインロールアウトポリシーについて検討し、アルゴリズムの計算複雑性を考察し、インデックス計算の複雑さと比較する。 数値的な例は、インデックスポリシーとロールアウトポリシーがミオピックポリシーよりも優れていることを示している。

関連論文リスト

• The Minimal Search Space for Conditional Causal Bandits [0.18124328823188351]
  因果知識は意思決定問題を支援するのに使える。 本稿では、最適条件介入を含むことが保証される最小限のノードのグラフィカルな特徴について述べる。 次に、この最小のノード群を特定するために、O(|V| + |E|)$の時間複雑性を持つ効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-10T15:45:18Z)
• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。 文脈問題を線形バンディット問題として解くことができることを示す。 この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
  論文  参考訳（メタデータ） (2022-11-08T22:18:53Z)
• 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)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
  両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。 本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-23T19:52:44Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)

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

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