論文の概要: Adversarial Online Multi-Task Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2301.04268v1
- Date: Wed, 11 Jan 2023 02:18:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-12 14:02:54.829097
- Title: Adversarial Online Multi-Task Reinforcement Learning
- Title(参考訳): オンラインマルチタスク強化学習
- Authors: Quan Nguyen and Nishant A. Mehta
- Abstract要約: 対戦型オンラインマルチタスク強化学習環境について考察する。
K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。
学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
- 参考スコア(独自算出の注目度): 12.421997449847153
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the adversarial online multi-task reinforcement learning setting,
where in each of $K$ episodes the learner is given an unknown task taken from a
finite set of $M$ unknown finite-horizon MDP models. The learner's objective is
to minimize its regret with respect to the optimal policy for each task. We
assume the MDPs in $\mathcal{M}$ are well-separated under a notion of
$\lambda$-separability, and show that this notion generalizes many
task-separability notions from previous works. We prove a minimax lower bound
of $\Omega(K\sqrt{DSAH})$ on the regret of any learning algorithm and an
instance-specific lower bound of $\Omega(\frac{K}{\lambda^2})$ in sample
complexity for a class of uniformly-good cluster-then-learn algorithms. We use
a novel construction called 2-JAO MDP for proving the instance-specific lower
bound. The lower bounds are complemented with a polynomial time algorithm that
obtains $\tilde{O}(\frac{K}{\lambda^2})$ sample complexity guarantee for the
clustering phase and $\tilde{O}(\sqrt{MK})$ regret guarantee for the learning
phase, indicating that the dependency on $K$ and $\frac{1}{\lambda^2}$ is
tight.
- Abstract(参考訳): 敵対的なオンラインマルチタスク強化学習の設定を考えると、k$のエピソードのそれぞれに、学習者は未知のタスクを与えられ、m$未知の有限ホライゾンmdpモデルから取得される。
学習者の目的は,各課題に対する最適方針に対する後悔を最小限に抑えることである。
我々は、$\mathcal{M}$ の MDP は $\lambda$-分離性の概念の下で十分に分離されていると仮定し、この概念が以前の研究から多くのタスク分離性の概念を一般化していることを示す。
我々は、任意の学習アルゴリズムの後悔に対して$\Omega(K\sqrt{DSAH})$のミニマックス下限と$\Omega(\frac{K}{\lambda^2})$のインスタンス固有の下限を、一様良質なクラスタ列学習アルゴリズムのクラスに対するサンプル複雑性で証明する。
2-JAO MDPと呼ばれる新しい構成を用いて、インスタンス固有の下界を証明する。
下限は、クラスタリングフェーズに対する$\tilde{o}(\frac{k}{\lambda^2})$のサンプル複雑性保証と、学習フェーズに対する$\tilde{o}(\sqrt{mk})$の保証を得る多項式時間アルゴリズムで補完され、$k$と$\frac{1}{\lambda^2}$への依存性がタイトであることを示している。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - 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 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) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure [9.759209713196718]
我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。
より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
論文 参考訳(メタデータ) (2022-06-07T20:39:51Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳(メタデータ) (2021-06-15T11:21:06Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-06-11T00:55:35Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。