論文の概要: Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost
- arxiv url: http://arxiv.org/abs/2202.06385v1
- Date: Sun, 13 Feb 2022 19:01:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-15 14:05:33.716415
- Title: Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost
- Title（参考訳）: loglog(t)スイッチングコストを用いたサンプル効率強化学習
- Authors: Dan Qiao, Ming Yin, Ming Min, Yu-Xiang Wang
- Abstract要約: 我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。
副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
- 参考スコア（独自算出の注目度）: 31.04961854943877
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of reinforcement learning (RL) with low (policy)
switching cost - a problem well-motivated by real-life RL applications in which
deployments of new policies are costly and the number of policy updates must be
low. In this paper, we propose a new algorithm based on stage-wise exploration
and adaptive policy elimination that achieves a regret of
$\widetilde{O}(\sqrt{H^4S^2AT})$ while requiring a switching cost of $O(HSA
\log\log T)$. This is an exponential improvement over the best-known switching
cost $O(H^2SA\log T)$ among existing methods with
$\widetilde{O}(\mathrm{poly}(H,S,A)\sqrt{T})$ regret. In the above, $S,A$
denotes the number of states and actions in an $H$-horizon episodic Markov
Decision Process model with unknown transitions, and $T$ is the number of
steps. We also prove an information-theoretical lower bound which says that a
switching cost of $\Omega(HSA)$ is required for any no-regret algorithm. As a
byproduct, our new algorithmic techniques allow us to derive a
\emph{reward-free} exploration algorithm with an optimal switching cost of
$O(HSA)$.
- Abstract（参考訳）: 本稿では,新しい政策の展開にコストがかかり,政策更新の回数も少なくなければならない実生活RLアプリケーションによって動機づけられた,低(政治的)スイッチングコストの強化学習(RL)問題について検討する。
本稿では,段階的探索と適応的ポリシー除去に基づく新しいアルゴリズムを提案する。これは$o(hsa \log\log t)$ の切り替えコストを必要とするが,$\widetilde{o}(\sqrt{h^4s^2at})$ の後悔を実現できる。
これは最もよく知られたスイッチングコストである$o(h^2sa\log t)$に対して、$\widetilde{o}(\mathrm{poly}(h,s,a)\sqrt{t})$で指数関数的に改善される。
上記の例では、$S,A$は、未知の遷移を持つ$H$-horizonエピソードマルコフ決定プロセスモデルにおける状態とアクションの数を表し、$T$はステップの数である。
また、任意の非回帰アルゴリズムに対して、スイッチングコストが$\Omega(HSA)$であることを示す情報理論の下限も証明する。
副産物として、我々の新しいアルゴリズム技術は、最適な切替コストが$O(HSA)$の 'emph{reward-free} 探索アルゴリズムを導出することができる。
関連論文リスト
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity
Constraints [21.412085244757336]
適応性制約を伴うマルチエージェント強化学習(MARL)の問題について検討する。
2つのプレイヤーゼロサムマルコフゲームに対して、$widetildeO(sqrtH3 S2 ABK)$を後悔する(政治)排除に基づくアルゴリズムを設計する。
バッチ複雑性の低い$Omega(fracHlog_AK+loglog K)$を$widetildeO(sqrtK)$で証明する。
論文 参考訳（メタデータ） (2024-02-02T03:00:40Z) - Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
本稿では, スイッチングコストを伴い, 効率の良いRLアルゴリズムの開発方法について述べる。
我々の下限は、敵RLのコストを切り替えるという根本的な課題のため、最も達成された後悔はもはや達成不可能であることを示している。
本稿では,遷移関数が知られているときの下位境界に一致することを後悔する2つの新しいスイッチング・リデュースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-08T23:41:29Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - 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) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。