論文の概要: Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2511.08097v1
• Date: Wed, 12 Nov 2025 01:39:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-12 20:17:03.644255
• Title: Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits
• Title（参考訳）: モデル予測制御は不均一レストレスマルチアームバンドに対してほぼ最適である
• Authors: Dheeraj Narasimha, Nicolas Gast,
• Abstract要約: ランダムなラウンドリングを持つ自然な有限水平LP更新ポリシーは、無限時間平均報酬問題において$O(log Nsqrt1/N)$Optimity gapを達成することを示す。 本研究は, 共分散性の概念を提唱し, 予測制御文学の手法を取り入れたものである。
• 参考スコア（独自算出の注目度）: 6.402634424631123
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider a general infinite horizon Heterogeneous Restless multi-armed Bandit (RMAB). Heterogeneity is a fundamental problem for many real-world systems largely because it resists many concentration arguments. In this paper, we assume that each of the $N$ arms can have different model parameters. We show that, under a mild assumption of uniform ergodicity, a natural finite-horizon LP-update policy with randomized rounding, that was originally proposed for the homogeneous case, achieves an $O(\log N\sqrt{1/N})$ optimality gap in infinite time average reward problems for fully heterogeneous RMABs. In doing so, we show results that provide strong theoretical guarantees on a well-known algorithm that works very well in practice. The LP-update policy is a model predictive approach that computes a decision at time $t$ by planing over a time-horizon $\{t\dots t+τ\}$. Our simulation section demonstrates that our algorithm works extremely well even when $τ$ is very small and set to $5$, which makes it computationally efficient. Our theoretical results draw on techniques from the model predictive control literature by invoking the concept of \emph{dissipativity} and generalize quite easily to the more general weakly coupled heterogeneous Markov Decision Process setting. In addition, we draw a parallel between our own policy and the LP-index policy by showing that the LP-index policy corresponds to $τ=1$. We describe where the latter's shortcomings arise from and how under our mild assumption we are able to address these shortcomings. The proof of our main theorem answers an open problem posed by (Brown et al 2020), paving the way for several new questions on the LP-update policies.
• Abstract（参考訳）: 一般無限地平線ヘテロジニアスレスマルチアームバンド (RMAB) を考える。 ヘテロジニティは、多くの濃度論に抵抗するため、多くの実世界のシステムにとって基本的な問題である。 本稿では、N$アームのそれぞれが異なるモデルパラメータを持つことができると仮定する。 我々は、一様エルゴディディティーの軽度な仮定の下で、ランダム化丸めの自然な有限水平LP更新ポリシーが、もともと同質なケースに対して提案され、完全不均一RMABに対する無限時間平均報酬問題において、$O(\log N\sqrt{1/N})$の最適性ギャップが得られることを示した。 その際、よく知られたアルゴリズムに強力な理論的保証を与える結果を示し、実際に非常によく機能する。 LP更新ポリシー(LP-update policy)は、時間軸の$\{t\dots t+τ\}$を計画することで、時刻のt$で決定を計算するモデル予測アプローチである。 シミュレーションセクションでは, τ$が非常に小さく, 5$に設定された場合でも, アルゴリズムが極めてうまく動作し, 計算効率が向上することを示した。 我々の理論的結果は、モデル予測制御文献から「emph{dissipativity}」の概念を呼び起こし、より一般的な弱結合なヘテロジニアスなマルコフ決定過程に非常に簡単に一般化することで、手法を導いた。 さらに、LP-インデックスポリシーが$τ=1$に対応することを示すことによって、当社のポリシーとLP-インデックスポリシーの並列性を示す。 私たちは、後者の欠点がどこから発生し、穏やかな仮定の下でこれらの欠点にどのように対処できるかを説明します。 私たちの主定理の証明は (Brown et al 2020) によって提起されたオープンな問題に答え、LP更新ポリシーに関するいくつかの新しい質問の道を開く。

関連論文リスト

• Model Predictive Control is Almost Optimal for Restless Bandit [2.295863158976069]
  離散時間無限水平平均報酬(RMAB)問題を考える。 本稿では, 回転型計算水平方向を$tau$とする非定常ポリシーを提案する。 局所安定性条件下では、その部分最適性ギャップは一般に$O(1/sqrtN)$、$exp(-Omega(N))$である。
  論文  参考訳（メタデータ） (2024-10-08T19:34:23Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption [12.471848976031904]
  基本的な目標は、腕の数($N$)が大きくなるにつれて、最適性のギャップを小さくするポリシーを効率的に計算することである。 既存の最適性に関する結果は、すべて一様大域的誘引特性(UGAP)に依存している。 我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-31T21:26:43Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)

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

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