論文の概要: Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption
- arxiv url: http://arxiv.org/abs/2405.17882v2
- Date: Thu, 17 Oct 2024 17:28:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-18 13:15:40.241159
- Title: Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption
- Title（参考訳）: グローバルアトラクタ推定を伴わない平均逆レストバンドの指数的漸近最適性獲得
- Authors: Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang,
- Abstract要約: 両腕の動的部分集合を2つ維持する新しいアンフツーセットポリシーを提案する。
2組のポリシーは、$O(exp(-C N)$Optimity gap for a $N$-armed problem で最適であることを示す。
- 参考スコア（独自算出の注目度）: 11.41663079285674
- License:
- Abstract: We consider the infinite-horizon average-reward restless bandit problem. We propose a novel \emph{two-set policy} that maintains two dynamic subsets of arms: one subset of arms has a nearly optimal state distribution and takes actions according to an Optimal Local Control routine; the other subset of arms is driven towards the optimal state distribution and gradually merged into the first subset. We show that our two-set policy is asymptotically optimal with an $O(\exp(-C N))$ optimality gap for an $N$-armed problem, under the mild assumptions of aperiodic-unichain, non-degeneracy, and local stability. Our policy is the first to achieve \emph{exponential asymptotic optimality} under the above set of easy-to-verify assumptions, whereas prior work either requires a strong \emph{global attractor} assumption or only achieves an $O(1/\sqrt{N})$ optimality gap. We further discuss obstacles in weakening the assumptions by demonstrating examples where exponential asymptotic optimality is not achievable when any of the three assumptions is violated. Notably, we prove a lower bound for a large class of locally unstable restless bandits, showing that local stability is particularly fundamental for exponential asymptotic optimality. Finally, we use simulations to demonstrate that the two-set policy outperforms previous policies on certain RB problems and performs competitively overall.
- Abstract（参考訳）: 無限水平平均逆レスバンディット問題を考える。
1つのアームのサブセットは、ほぼ最適な状態分布を持ち、最適局所制御ルーチンに従ってアクションを取る;もう1つのアームのサブセットは、最適な状態分布に向かって駆動され、徐々に第1サブセットにマージされる。
我々は、周期的ユニチェーン、非縮退性、局所安定性の軽度な仮定の下で、我々の2組のポリシーが、$O(\exp(-C N))$$ N$の武装問題に対して漸近的に最適であることを示す。
我々の政策は、上記の一組の検証が容易な仮定の下で最初に \emph{exponential asymptotic optimality} を達成する一方、事前の作業は強い \emph{global attractor} の仮定を必要とするか、あるいは$O(1/\sqrt{N}) の最適性ギャップしか達成しない。
さらに、3つの仮定のいずれかに違反した場合に指数的漸近的最適性が達成できない例を示すことによって、仮定を弱める際の障害についても論じる。
特に、局所的不安定なレスレス・バンディットの大きなクラスに対する低い境界を証明し、局所的な安定性が指数的漸近的最適性に特に重要であることを示す。
最後に、シミュレーションを用いて、この2セットポリシーが特定のRB問題に対する以前のポリシーより優れており、総合的に競争力があることを示す。
関連論文リスト
- 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) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (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) - The Role of Baselines in Policy Gradient Optimization [83.42050606055822]
Emphstateのバリューベースラインが、オン・ポリティクスを可能にしていることを示す。
世界的な最適な政策勾配(NPG)に収束する。
O (1/t) レート勾配でのポリシー。
値ベースラインの主な効果は、その分散ではなく、更新のアグレッシブさをthabfreduceすることにある。
論文 参考訳（メタデータ） (2023-01-16T06:28:00Z) - On Gap-dependent Bounds for Offline Reinforcement Learning [40.92345387517103]
本稿では,オフライン強化学習におけるギャップ依存型サンプル複雑性の系統的研究を行う。
最適政策カバレッジの仮定の下では、最適な$Q$-函数に正の準最適差がある場合、その値は$Oleft(frac1epsilonright)$に改善することができる。
最適政策の訪問確率が正である状態に対して,行動政策の訪問確率が一様に低い場合,最適政策を特定する際のサンプルの複雑さは$frac1epsilon$とは無関係である。
論文 参考訳（メタデータ） (2022-06-01T01:44:12Z) - Near-optimality for infinite-horizon restless bandits with many arms [19.12759228067286]
レスト・バンディットは、レコメンデーター・システム、アクティブ・ラーニング、収益管理などの分野での応用に関する問題である。
我々は、$O(sqrtN)$Optimity gapを持つ流体均衡政策と呼ばれる政策のクラスを導出する。
また,流体バランスポリシが特定の問題に対して最先端のパフォーマンスを実現することを実証的に示す。
論文 参考訳（メタデータ） (2022-03-29T18:49:21Z) - Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium
Learning from Offline Datasets [101.5329678997916]
両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。
目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
論文 参考訳（メタデータ） (2022-02-15T15:39:30Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
論文 参考訳（メタデータ） (2021-07-25T23:27:12Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。