論文の概要: Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in
Multi-Agent RL and Inventory Control
- arxiv url: http://arxiv.org/abs/2010.03161v4
- Date: Sat, 20 Aug 2022 02:54:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-09 21:53:48.843714
- Title: Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in
Multi-Agent RL and Inventory Control
- Title（参考訳）: モデルフリー非定常RL:準最適レグレットとマルチエージェントRLおよびインベントリ制御への応用
- Authors: Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, Tamer
Ba\c{s}ar
- Abstract要約: 非定常RLのための最初のモデルフリーアルゴリズムであるアッパー信頼境界を用いたリスタートQラーニング(RestartQ-UCB)を提案する。
我々は,情報理論的下限を$Omega(Sfrac13 Afrac13 Deltafrac13 Hfrac23 Tfrac23)$,非定常RLで最初の下限を設定すれば,アルゴリズムが最適であることを示す。
- 参考スコア（独自算出の注目度）: 28.80743320843154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider model-free reinforcement learning (RL) in non-stationary Markov
decision processes. Both the reward functions and the state transition
functions are allowed to vary arbitrarily over time as long as their cumulative
variations do not exceed certain variation budgets. We propose Restarted
Q-Learning with Upper Confidence Bounds (RestartQ-UCB), the first model-free
algorithm for non-stationary RL, and show that it outperforms existing
solutions in terms of dynamic regret. Specifically, RestartQ-UCB with
Freedman-type bonus terms achieves a dynamic regret bound of
$\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H
T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions,
respectively, $\Delta>0$ is the variation budget, $H$ is the number of time
steps per episode, and $T$ is the total number of time steps. We further
present a parameter-free algorithm named Double-Restart Q-UCB that does not
require prior knowledge of the variation budget. We show that our algorithms
are \emph{nearly optimal} by establishing an information-theoretical lower
bound of $\Omega(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}}
H^{\frac{2}{3}} T^{\frac{2}{3}})$, the first lower bound in non-stationary RL.
Numerical experiments validate the advantages of RestartQ-UCB in terms of both
cumulative rewards and computational efficiency. We demonstrate the power of
our results in examples of multi-agent RL and inventory control across related
products.
- Abstract（参考訳）: 非定常マルコフ決定過程におけるモデルフリー強化学習(rl)を考える。
報酬関数と状態遷移関数の両方は、累積変動が特定の変動予算を超えない限り、時間とともに任意に変化することが許される。
本研究では,非定常rlのためのモデルフリーなアルゴリズムであるuper confidence bounds (restartq-ucb) を用いたq-learningの再開を提案する。
具体的には、freedman型のボーナス項を持つrelayq-ucbは$\widetilde{o}(s^{\frac{1}{3}} a^{\frac{1}{3}} \delta^{\frac{1}{3}} h t^{\frac{2}{3}})$であり、ここで$s$と$a$は状態とアクションの数であり、$\delta>0$は変動予算、$h$はエピソードごとの時間ステップの数、$t$は時間ステップの総数である。
さらに、変動予算の事前知識を必要としないDouble-Restart Q-UCBというパラメータフリーアルゴリズムを提案する。
我々のアルゴリズムは、非定常rlにおける最初の下界である$\omega(s^{\frac{1}{3}} a^{\frac{1}{3}} \delta^{\frac{1}{3}} h^{\frac{2}{3}} t^{\frac{2}{3}} t^{\frac{2}{3}})$という情報理論上の下界を確立することによって、 \emph{nearly optimal} であることが示されている。
数値実験は、累積報酬と計算効率の両方の観点からRestartQ-UCBの利点を検証する。
我々は,マルチエージェントrlと関連製品間の在庫管理の例で,結果のパワーを実証する。
関連論文リスト
- Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
本稿では, スイッチングコストを伴い, 効率の良いRLアルゴリズムの開発方法について述べる。
我々の下限は、敵RLのコストを切り替えるという根本的な課題のため、最も達成された後悔はもはや達成不可能であることを示している。
本稿では,遷移関数が知られているときの下位境界に一致することを後悔する2つの新しいスイッチング・リデュースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-08T23:41:29Z) - Bridging Distributional and Risk-sensitive Reinforcement Learning with
Provable Regret Bounds [24.571530193140916]
エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。
モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。
いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
論文 参考訳（メタデータ） (2022-10-25T14:30:48Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Optimal Dynamic Regret in LQR Control [23.91519151164528]
我々は、LQR制御という2次的損失の連続を伴う非確率的制御の問題を考察する。
我々は、$tildeO(textmaxn1/3 MathcalTV(M_1:n)2/3, 1)$の最適動的(政治的)後悔を実現するオンラインアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-06-18T18:00:21Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - A Provably-Efficient Model-Free Algorithm for Constrained Markov
Decision Processes [13.877420496703627]
本稿では,制約付きマルコフ決定過程(CMDP)に対するモデルフリーでシミュレータフリーな強化学習アルゴリズムを提案する。
このアルゴリズムは、累積報酬のQ-関数、制約の累積効用Q-関数、累積制約違反を推定する仮想キューの3つの主要な成分を持つため、トリプルQと名付けられた。
論文 参考訳（メタデータ） (2021-06-03T03:53:27Z) - 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) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Learning in Markov Decision Processes under Constraints [34.03325546283489]
本稿では,マルコフプロセスによってモデル化された環境とエージェントが繰り返し対話するマルコフ決定過程における強化学習について考察する。
我々は,累積報酬をT$タイムステップで最大化するモデルベースRLアルゴリズムを設計する。
我々は、報酬の後悔と残りのコストの増大を犠牲にして、M$コストの所望のサブセットの後悔を減らす方法を示す。
論文 参考訳（メタデータ） (2020-02-27T20:58:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。