論文の概要: Learning in Markov Decision Processes under Constraints
- arxiv url: http://arxiv.org/abs/2002.12435v5
- Date: Wed, 5 Jan 2022 19:21:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 08:13:54.641080
- Title: Learning in Markov Decision Processes under Constraints
- Title(参考訳): マルコフ決定過程における制約下での学習
- Authors: Rahul Singh, Abhishek Gupta and Ness B. Shroff
- Abstract要約: 本稿では,マルコフプロセスによってモデル化された環境とエージェントが繰り返し対話するマルコフ決定過程における強化学習について考察する。
我々は,累積報酬をT$タイムステップで最大化するモデルベースRLアルゴリズムを設計する。
我々は、報酬の後悔と残りのコストの増大を犠牲にして、M$コストの所望のサブセットの後悔を減らす方法を示す。
- 参考スコア(独自算出の注目度): 34.03325546283489
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider reinforcement learning (RL) in Markov Decision Processes in which
an agent repeatedly interacts with an environment that is modeled by a
controlled Markov process. At each time step $t$, it earns a reward, and also
incurs a cost-vector consisting of $M$ costs. We design model-based RL
algorithms that maximize the cumulative reward earned over a time horizon of
$T$ time-steps, while simultaneously ensuring that the average values of the
$M$ cost expenditures are bounded by agent-specified thresholds
$c^{ub}_i,i=1,2,\ldots,M$.
In order to measure the performance of a reinforcement learning algorithm
that satisfies the average cost constraints, we define an $M+1$ dimensional
regret vector that is composed of its reward regret, and $M$ cost regrets. The
reward regret measures the sub-optimality in the cumulative reward, while the
$i$-th component of the cost regret vector is the difference between its $i$-th
cumulative cost expense and the expected cost expenditures $Tc^{ub}_i$.
We prove that the expected value of the regret vector of UCRL-CMDP, is
upper-bounded as $\tilde{O}\left(T^{2\slash 3}\right)$, where $T$ is the time
horizon. We further show how to reduce the regret of a desired subset of the
$M$ costs, at the expense of increasing the regrets of rewards and the
remaining costs. To the best of our knowledge, ours is the only work that
considers non-episodic RL under average cost constraints, and derive algorithms
that can~\emph{tune the regret vector} according to the agent's requirements on
its cost regrets.
- Abstract(参考訳): エージェントが制御されたマルコフプロセスによってモデル化された環境と繰り返し相互作用するマルコフ決定過程における強化学習(rl)を考える。
それぞれのステップ$t$で報酬を受け取り、また$M$のコストでコストベクターを発生させる。
モデルに基づくRLアルゴリズムは, 累積報酬をT$タイムステップで最大化するとともに, M$コスト支出の平均値がエージェント指定閾値$c^{ub}_i,i=1,2,\ldots,M$で有界であることを保証する。
平均的なコスト制約を満たす強化学習アルゴリズムの性能を測定するために、その報酬の後悔と、その報酬の後悔からなる、m+1$次元の後悔ベクトルとを定義する。
報酬の後悔は累積報酬の最適化度を測定し、コストの後悔のベクトルの第1の要素は、その第1の累積コストコストコストと、期待されるコストの支出である$tc^{ub}_i$との違いである。
ucrl-cmdp の後悔ベクトルの期待値が $\tilde{o}\left(t^{2\slash 3}\right)$ で上限値であることを証明する。
私たちはさらに、報酬の後悔と残りのコストの増加を犠牲にして、m$コストの所望のサブセットの後悔を減らす方法を示します。
我々の知る限りでは、我々の仕事は平均的なコスト制約の下で非エポゾディックなRLを考える唯一の仕事であり、そのコストの後悔に対するエージェントの要求に応じて–\emph{tune the regret vector} を導出するアルゴリズムである。
関連論文リスト
- Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
本稿では,新しいコストと報酬関数推定器に基づくモデルベースアルゴリズムを提案する。
我々のアルゴリズムは、$widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$の残念な上限を達成する。
論文 参考訳(メタデータ) (2024-10-14T04:51:06Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳(メタデータ) (2022-10-20T21:32:01Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳(メタデータ) (2021-04-22T17:20:48Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳(メタデータ) (2021-03-24T10:11:49Z) - Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in
Multi-Agent RL and Inventory Control [28.80743320843154]
非定常RLのための最初のモデルフリーアルゴリズムであるアッパー信頼境界を用いたリスタートQラーニング(RestartQ-UCB)を提案する。
我々は,情報理論的下限を$Omega(Sfrac13 Afrac13 Deltafrac13 Hfrac23 Tfrac23)$,非定常RLで最初の下限を設定すれば,アルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2020-10-07T04:55:56Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。