論文の概要: When is exponential asymptotic optimality achievable in average-reward restless bandits?

• arxiv url: http://arxiv.org/abs/2405.17882v1
• Date: Tue, 28 May 2024 07:08:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 20:07:07.480432
• Title: When is exponential asymptotic optimality achievable in average-reward restless bandits?
• Title（参考訳）: 平均逆レスベルトバンドにおける指数的漸近最適性はいつ達成できるか?
• Authors: Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang,
• Abstract要約: 我々は,$O(exp(-C N))$Optimity gap for a $N$-armed problem。 我々の政策は、上記の容易に検証できる仮定の下で指数的最適性を初めて達成する一方、事前の作業は強いグローバルアトラクタ仮定を必要とするか、あるいは$O(sqrtN)$最適性ギャップしか達成しない。
• 参考スコア（独自算出の注目度）: 11.41663079285674
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the discrete-time infinite-horizon average-reward restless bandit problem. We propose a novel 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 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 exponential asymptotic optimality under the above set of easy-to-verify assumptions, whereas prior work either requires a strong Global Attractor assumption or only achieves an $O(1/\sqrt{N})$ optimality gap. We further discuss the fundamental obstacles in significantly weakening our assumptions. In particular, we prove a lower bound showing that local stability is fundamental for exponential asymptotic optimality.
• Abstract（参考訳）: 離散時間無限水平平均逆レスバンドイット問題を考える。 1つのアームのサブセットは、ほぼ最適な状態分布を持ち、最適局所制御ルーチンに従ってアクションを取る;もう1つのアームのサブセットは、最適な状態分布に向けて駆動され、徐々に第1サブセットにマージされる。 我々は, 周期的ユニチェーン, 非縮退性, 局所安定性の軽度な仮定の下で, $O(\exp(-C N))$$ N$武器問題に対する最適性ギャップが漸近的に最適であることを示す。 我々の政策は、上記の一組の検証が容易な仮定の下で指数的漸近的最適性を達成する最初のものであるが、事前の作業は強いグローバル・アトラクタの仮定を必要とするか、あるいは$O(1/\sqrt{N})$の最適性ギャップしか達成しない。 さらに、仮定を著しく弱めるための基本的な障害についても論じる。 特に、局所的な安定性が指数的漸近的最適性の基本であることを証明している。

関連論文リスト

• 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)

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

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