論文の概要: Lagrangian Relaxation for Multi-Action Partially Observable Restless Bandits: Heuristic Policies and Indexability
- arxiv url: http://arxiv.org/abs/2509.00415v1
- Date: Sat, 30 Aug 2025 08:47:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 15:17:03.222054
- Title: Lagrangian Relaxation for Multi-Action Partially Observable Restless Bandits: Heuristic Policies and Indexability
- Title（参考訳）: 多成分部分観察可能なレストレスバンドに対するラグランジアン緩和法:ヒューリスティック・ポリシーと指数性
- Authors: Rahul Meshram, Kesav Kaza,
- Abstract要約: 本研究では,多動作部分観察可能なレストレスマルチアームバンドについて検討した。
バンディットの状態は観測できないが、有限個のフィードバック信号のうちの1つは観測可能である。
有限状態有限作用 POMDP に対する最適値関数の計算は非自明である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partially observable restless multi-armed bandits have found numerous applications including in recommendation systems, communication systems, public healthcare outreach systems, and in operations research. We study multi-action partially observable restless multi-armed bandits, it is a generalization of the classical restless multi-armed bandit problem -- 1) each bandit has finite states, and the current state is not observable, 2) each bandit has finite actions. In particular, we assume that more than two actions are available for each bandit. We motivate our problem with the application of public-health intervention planning. We describe the model and formulate a long term discounted optimization problem, where the state of each bandit evolves according to a Markov process, and this evolution is action dependent. The state of a bandit is not observable but one of finitely many feedback signals are observable. Each bandit yields a reward, based on the action taken on that bandit. The agent is assumed to have a budget constraint. The bandits are assumed to be independent. However, they are weakly coupled at the agent through the budget constraint. We first analyze the Lagrangian bound method for our partially observable restless bandits. The computation of optimal value functions for finite-state, finite-action POMDPs is non-trivial. Hence, the computation of Lagrangian bounds is also challenging. We describe approximations for the computation of Lagrangian bounds using point based value iteration (PBVI) and online rollout policy. We further present various properties of the value functions and provide theoretical insights on PBVI and online rollout policy. We study heuristic policies for multi-actions PORMAB. Finally, we discuss present Whittle index policies and their limitations in our model.
- Abstract（参考訳）: 部分的に観察可能なレストレスのマルチアームバンドは、レコメンデーションシステム、通信システム、公衆医療のアウトリーチシステム、オペレーションリサーチなど、数多くの応用を見出している。
我々は、古典的なレストレス・マルチアーム・バンディット問題の一般化である、可観測な部分的なレストレス・マルチアーム・バンディットについて研究する。
1) 各帯域は有限状態であり、現在の状態は観測不可能である。
2) 各帯域は有限の作用を持つ。
特に、バンディットごとに2つ以上のアクションが利用できると仮定する。
我々は、公衆衛生介入計画の適用により、我々の問題を動機づける。
このモデルを記述し,各帯域の状態がマルコフ過程に従って進化する長期割引最適化問題を定式化し,この進化は行動依存である。
バンディットの状態は観測できないが、有限個のフィードバック信号のうちの1つは観測可能である。
各バンドイットは、そのバンドイットで取られた行動に基づいて報酬を得る。
その代理人は予算の制約があると仮定される。
盗賊は独立していると推定される。
しかし、彼らは予算制約によってエージェントに弱い結びつきがある。
まず,ラグランジアン境界法を部分的に観測可能なレスト・バンディットに対して解析する。
有限状態有限作用 POMDP に対する最適値関数の計算は非自明である。
したがって、ラグランジュ境界の計算も困難である。
本稿では,点ベース値反復(PBVI)とオンラインロールアウトポリシを用いたラグランジアン境界の計算法について述べる。
さらに、価値関数の様々な特性を示し、PBVIおよびオンラインロールアウトポリシーに関する理論的洞察を提供する。
マルチアクションPORMABに対するヒューリスティックポリシーについて検討する。
最後に、現在のWhittleインデックスポリシーとそのモデルにおける制限について論じる。
関連論文リスト
- Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms [80.05851139852311]
本稿では,ガウス的手法を用いて連続空間上の報酬環境を学習するための新しいポリシーを提案する。
提案手法は,$mathcalO*(sqrtT)$ cumulative regret を用いて連続リプシッツ報酬関数を効率よく学習することを示す。
論文 参考訳（メタデータ） (2025-05-30T15:15:18Z) - Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback [11.262167746929332]
Restless Multi-armed bandits (RMAB)は、シーケンシャルな意思決定問題のモデル化において中心的な役割を果たす。
本稿では,未知の遷移関数と対向報酬を持つ表在的RMABにおける学習課題について考察する。
我々は2つの重要な貢献者による新しい強化学習アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-05-02T02:20:19Z) - Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Indexability of Finite State Restless Multi-Armed Bandit and Rollout
Policy [5.64327489637232]
有限状態定常多武装バンディット問題を考える。
レスレス・バンディットに対する古典的なアプローチは、Whittle Index Policyである。
本稿では,単一武装バンディットモデルの指標基準を検証するための代替手法を提案する。
論文 参考訳（メタデータ） (2023-04-30T06:53:44Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-03-06T20:34:42Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。