Fugu-MT 論文翻訳(概要): Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits

論文の概要: Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits

arxiv url: http://arxiv.org/abs/2402.05689v3
Date: Thu, 03 Oct 2024 17:37:33 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-04 23:27:06.173657
Title: Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits
Title（参考訳）: 一重鎖と周期性は平均逆レスベルトの漸近最適性に十分である
Authors: Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang,
Abstract要約: 我々のポリシーは、$O(1/sqrtN)$Optimity gap for a $N$-armed problemで最適であることを示す。当社のアプローチは、インデックスや優先順位ポリシーに重点を置く既存の作業から逸脱しています。
参考スコア（独自算出の注目度）: 11.41663079285674
License:
Abstract: We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are asymptotically optimal with an $O(1/\sqrt{N})$ optimality gap for an $N$-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which rely on the Global Attractor Property (GAP) to guarantee convergence to the optimum, or a recently developed simulation-based policy, which requires a Synchronization Assumption (SA).
Abstract（参考訳）: 無限水平平均逆レスバンディット問題を離散時間で考える。我々は、最適な分布に向けて、徐々に大きな武器のサブセットを推し進めるために設計された新しいポリシーのクラスを提案する。我々は、我々のポリシーが、一鎖と周期性の仮定のみを仮定して、$O(1/\sqrt{N})$最適性ギャップを$N$武装問題に対して漸近的に最適であることを示す。提案手法は,グローバル・アトラクタ・プロパティ (GAP) に頼って,最適化への収束を保証する,あるいはシンクロナイゼーション・アセスメント (SA) を必要とする最近開発されたシミュレーション・ベースの政策である。

関連論文リスト

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)
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)
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)
Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
論文参考訳（メタデータ） (2022-10-03T16:05:43Z)
Near-optimality for infinite-horizon restless bandits with many arms [19.12759228067286]
レスト・バンディットは、レコメンデーター・システム、アクティブ・ラーニング、収益管理などの分野での応用に関する問題である。我々は、$O(sqrtN)$Optimity gapを持つ流体均衡政策と呼ばれる政策のクラスを導出する。また,流体バランスポリシが特定の問題に対して最先端のパフォーマンスを実現することを実証的に示す。
論文参考訳（メタデータ） (2022-03-29T18:49:21Z)
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)
CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
安全強化学習(SRL)問題では、エージェントは期待される全報酬を最大化し、一定の制約の違反を避けるために環境を探索する。これは、大域的最適ポリシーを持つSRLアルゴリズムの最初の分析である。
論文参考訳（メタデータ） (2020-11-11T16:05:14Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)

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