論文の概要: Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption

• arxiv url: http://arxiv.org/abs/2306.00196v2
• Date: Sun, 10 Dec 2023 05:59:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 02:32:56.645737
• Title: Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
• Title（参考訳）: 平均的リワードを伴うレストレスバンド:一様グローバルアトラクタの推計を破る
• Authors: Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang
• Abstract要約: 本研究では、離散時間と連続時間の両方の設定の下で、平均報酬基準による無限水平レストバンド問題について検討する。 我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。 どちらの設定でも、私たちの仕事はUGAPを必要としない最初の最適性の結果です。
• 参考スコア（独自算出の注目度）: 12.471848976031904
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the infinite-horizon Restless Bandit problem with the average reward criterion, under both discrete-time and continuous-time settings. A fundamental goal is to design computationally efficient policies that achieve a diminishing optimality gap as the number of arms, $N$, grows large. Existing results on asymptotic optimality all rely on the uniform global attractor property (UGAP), a complex and challenging-to-verify assumption. In this paper, we propose a general, simulation-based framework, Follow-the-Virtual-Advice, that converts any single-armed policy into a policy for the original $N$-armed problem. This is done by simulating the single-armed policy on each arm and carefully steering the real state towards the simulated state. Our framework can be instantiated to produce a policy with an $O(1/\sqrt{N})$ optimality gap. In the discrete-time setting, our result holds under a simpler synchronization assumption, which covers some problem instances that violate UGAP. More notably, in the continuous-time setting, we do not require any additional assumptions beyond the standard unichain condition. In both settings, our work is the first asymptotic optimality result that does not require UGAP.
• Abstract（参考訳）: 平均報酬基準による無限ホリゾンレストレスト・バンディット問題を離散時間と連続時間の両方の設定で検討した。 基本的な目標は、腕の数($n$)が大きくなるにつれて最適なギャップを減少させる計算効率のよいポリシーを設計することである。 漸近的最適性に関する既存の結果は、すべて一様大域的誘引特性(UGAP)に依存している。 本稿では,単腕のポリシを元のn$-armed問題に対するポリシに変換する,汎用的なシミュレーションベースのフレームワークであるnext-the-virtual-adviceを提案する。 これは、各腕に単一武装のポリシーをシミュレートし、実状態をシミュレートされた状態に向けて慎重に操ることによって行われる。 我々のフレームワークは、$O(1/\sqrt{N})$Optimity gapでポリシーを生成するためにインスタンス化することができる。 離散時間設定では、結果はより単純な同期仮定の下で保持され、これはugapに違反する問題インスタンスをカバーする。 より注目すべきは、連続時間設定では、標準のユニチェーン条件を超える追加の仮定は不要である。 どちらの設定でも、我々の研究はUGAPを必要としない最初の漸近的最適性の結果である。

関連論文リスト

• Model Predictive Control is Almost Optimal for Restless Bandit [2.295863158976069]
  離散時間無限水平平均報酬(RMAB)問題を考える。 本稿では, 回転型計算水平方向を$tau$とする非定常ポリシーを提案する。 局所安定性条件下では、その部分最適性ギャップは一般に$O(1/sqrtN)$、$exp(-Omega(N))$である。
  論文  参考訳（メタデータ） (2024-10-08T19:34:23Z)
• Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption [11.41663079285674]
  両腕の動的部分集合を2つ維持する新しいアンフツーセットポリシーを提案する。 2組のポリシーは、$O(exp(-C N)$Optimity gap for a $N$-armed problem で最適であることを示す。
  論文  参考訳（メタデータ） (2024-05-28T07:08:29Z)
• Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits [11.41663079285674]
  我々のポリシーは、$O(1/sqrtN)$Optimity gap for a $N$-armed problemで最適であることを示す。 当社のアプローチは、インデックスや優先順位ポリシーに重点を置く既存の作業から逸脱しています。
  論文  参考訳（メタデータ） (2024-02-08T14:07:20Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• 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)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。 次に,政策最適化におけるコミット率の概念を紹介する。 第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
  論文  参考訳（メタデータ） (2021-10-29T06:35:44Z)
• Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
  有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。 最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。 最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
  論文  参考訳（メタデータ） (2021-07-25T23:27:12Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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