論文の概要: On learning Whittle index policy for restless bandits with scalable regret

• arxiv url: http://arxiv.org/abs/2202.03463v2
• Date: Wed, 26 Apr 2023 23:46:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-28 21:54:36.318199
• Title: On learning Whittle index policy for restless bandits with scalable regret
• Title（参考訳）: ゆるやかな後悔を伴うレスレスブレイディットに対するウィトル指数の学習について
• Authors: Nima Akbarzadeh, Aditya Mahajan
• Abstract要約: 強化学習は、優れたリソース割り当てとスケジューリングポリシーを学ぶための魅力的なアプローチである。 ほとんどのRLアルゴリズムの累積後悔は$tilde O(mathsfS sqrtmathsfA T)$、$mathsfS$は状態空間のサイズである。 本稿では,このような問題に対するモデルベースRLアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 1.0152838128195465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system model is unknown. However, the cumulative regret of most RL algorithms scales as $\tilde O(\mathsf{S} \sqrt{\mathsf{A} T})$, where $\mathsf{S}$ is the size of the state space, $\mathsf{A}$ is the size of the action space, $T$ is the horizon, and the $\tilde{O}(\cdot)$ notation hides logarithmic terms. Due to the linear dependence on the size of the state space, these regret bounds are prohibitively large for resource allocation and scheduling problems. In this paper, we present a model-based RL algorithm for such problems which has scalable regret. In particular, we consider a restless bandit model, and propose a Thompson-sampling based learning algorithm which is tuned to the underlying structure of the model. We present two characterizations of the regret of the proposed algorithm with respect to the Whittle index policy. First, we show that for a restless bandit with $n$ arms and at most $m$ activations at each time, the regret scales either as $\tilde{O}(mn\sqrt{T})$ or $\tilde{O}(n^2 \sqrt{T})$ depending on the reward model. Second, under an additional technical assumption, we show that the regret scales as $\tilde{O}(n^{1.5} \sqrt{T})$ or $\tilde{O}(\max\{m\sqrt{n}, n\} \sqrt{T})$. We present numerical examples to illustrate the salient features of the algorithm.
• Abstract（参考訳）: 強化学習は、システムモデルが不明なときにデータに基づいて、優れたリソース割り当てとスケジューリングポリシーを学ぶための魅力的なアプローチである。 しかし、ほとんどのrlアルゴリズムの累積後悔は$\tilde o(\mathsf{s} \sqrt{\mathsf{a} t})$であり、ここで$\mathsf{s}$は状態空間の大きさ、$\mathsf{a}$はアクション空間のサイズ、$t$は地平線、$\tilde{o}(\cdot)$記法は対数項を隠す。 状態空間の大きさに線形依存するため、これらの後悔の限界はリソースの割り当てやスケジューリングの問題に対して非常に大きい。 本稿では,このような問題に対してスケーラブルなモデルベースrlアルゴリズムを提案する。 特に,restless banditモデルについて検討し,モデルの基盤構造に適応したトンプソンサンプリングに基づく学習アルゴリズムを提案する。 本稿では,Whittleインデックスポリシーに対する提案アルゴリズムの後悔の2つの特徴について述べる。 まず、n$のアームと最大$m$のアクティベーションを持つレストレスのバンディットに対して、後悔は、報酬モデルによって$\tilde{o}(mn\sqrt{t})$または$\tilde{o}(n^2 \sqrt{t})$となる。 第二に、追加の技術的仮定の下で、後悔は$\tilde{O}(n^{1.5} \sqrt{T})$または$\tilde{O}(\max\{m\sqrt{n}, n\} \sqrt{T})$としてスケールすることを示す。 本稿では,アルゴリズムの有意な特徴を示す数値例を示す。

関連論文リスト

• Reinforcement Learning and Regret Bounds for Admission Control [0.08192907805418585]
  強化学習アルゴリズムの期待された後悔は、未計算の戻り値に対して$Omegaleft(sqrtDXATright)$で制限される。 UCRL2にインスパイアされたアルゴリズムを提案し、その問題の構造を用いて、有限サーバの場合、$O(Slog T + sqrtmT log T)$で期待される全後悔を上位に制限する。
  論文  参考訳（メタデータ） (2024-06-07T09:09:14Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes [21.77276136591518]
  我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。 シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
  論文  参考訳（メタデータ） (2023-06-28T17:43:19Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
  一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。 提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。 まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
  論文  参考訳（メタデータ） (2021-01-06T18:56:07Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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