論文の概要: Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space

• arxiv url: http://arxiv.org/abs/2302.10667v1
• Date: Tue, 21 Feb 2023 13:28:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-22 15:12:47.610446
• Title: Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space
• Title（参考訳）: 出生・死亡過程における強化学習:国家空間への依存を破る
• Authors: Jonatha Anselmi (POLARIS, LIG), Bruno Gaujal (POLARIS, LIG), Louis-S\'ebastien Rebuffi (POLARIS, LIG, UGA)
• Abstract要約: 我々は、出生・死亡構造を有するMDPにおける未報告の強化学習の後悔を再考する。 本研究の結果から,従来の学習アルゴリズム sc Ucrl2 のやや遅れたバージョンに対する後悔は,実際には $tildemathcalO(sqrtEAT)$ で表される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we revisit the regret of undiscounted reinforcement learning in MDPs with a birth and death structure. Specifically, we consider a controlled queue with impatient jobs and the main objective is to optimize a trade-off between energy consumption and user-perceived performance. Within this setting, the \emph{diameter} $D$ of the MDP is $\Omega(S^S)$, where $S$ is the number of states. Therefore, the existing lower and upper bounds on the regret at time$T$, of order $O(\sqrt{DSAT})$ for MDPs with $S$ states and $A$ actions, may suggest that reinforcement learning is inefficient here. In our main result however, we exploit the structure of our MDPs to show that the regret of a slightly-tweaked version of the classical learning algorithm {\sc Ucrl2} is in fact upper bounded by $\tilde{\mathcal{O}}(\sqrt{E_2AT})$ where $E_2$ is related to the weighted second moment of the stationary measure of a reference policy. Importantly, $E_2$ is bounded independently of $S$. Thus, our bound is asymptotically independent of the number of states and of the diameter. This result is based on a careful study of the number of visits performed by the learning algorithm to the states of the MDP, which is highly non-uniform.
• Abstract（参考訳）: 本稿では、出生・死亡構造を持つMDPにおける、未報告の強化学習の後悔を再考する。 具体的には,過度なジョブを伴う制御キューについて検討し,エネルギー消費とユーザ知覚性能のトレードオフを最適化することを目的としている。 この設定の中で MDP の \emph{diameter} $D$ は $\Omega(S^S)$ であり、$S$ は状態の数である。 したがって、T$(\sqrt{DSAT})$$S$状態のMDPと$A$動作の既存の下限と上限は、強化学習が非効率であることを示唆している。 しかし,本研究の主な結果では,mdpの構造を利用して,古典的学習アルゴリズム「sc ucrl2}」のわずかに曲がりくねったバージョンに対する後悔が,実のところ$\tilde{\mathcal{o}}(\sqrt{e_2at})$で上限されていることを示す。 重要なのは、$E_2$は$S$とは独立にバウンドされる。 したがって、我々の境界は漸近的に状態の数と直径に独立である。 この結果は、学習アルゴリズムによるMDPの状態への訪問回数を慎重に研究することに基づいており、これは非常に一様ではない。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
  平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。 我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
  論文  参考訳（メタデータ） (2023-11-22T15:34:44Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
  UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。 さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
  論文  参考訳（メタデータ） (2020-10-01T17:57:47Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。 我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-29T02:02:40Z)

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

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