論文の概要: Online learning in MDPs with linear function approximation and bandit
feedback
- arxiv url: http://arxiv.org/abs/2007.01612v2
- Date: Sat, 12 Jun 2021 19:28:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 04:34:39.992600
- Title: Online learning in MDPs with linear function approximation and bandit
feedback
- Title（参考訳）: 線形関数近似と帯域フィードバックを用いたMDPにおけるオンライン学習
- Authors: Gergely Neu and Julia Olkhovskaya
- Abstract要約: 我々は,学習者がマルコフ決定プロセスと一連のエピソードで対話するオンライン学習問題を考える。
我々は, MDP-LinExp3 が, この問題設定のための最初の証明可能なアルゴリズムであることを示す。
- 参考スコア（独自算出の注目度）: 13.32560004325655
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider an online learning problem where the learner interacts with a
Markov decision process in a sequence of episodes, where the reward function is
allowed to change between episodes in an adversarial manner and the learner
only gets to observe the rewards associated with its actions. We allow the
state space to be arbitrarily large, but we assume that all action-value
functions can be represented as linear functions in terms of a known
low-dimensional feature map, and that the learner has access to a simulator of
the environment that allows generating trajectories from the true MDP dynamics.
Our main contribution is developing a computationally efficient algorithm that
we call MDP-LinExp3, and prove that its regret is bounded by
$\widetilde{\mathcal{O}}\big(H^2 T^{2/3} (dK)^{1/3}\big)$, where $T$ is the
number of episodes, $H$ is the number of steps in each episode, $K$ is the
number of actions, and $d$ is the dimension of the feature map. We also show
that the regret can be improved to $\widetilde{\mathcal{O}}\big(H^2
\sqrt{TdK}\big)$ under much stronger assumptions on the MDP dynamics. To our
knowledge, MDP-LinExp3 is the first provably efficient algorithm for this
problem setting.
- Abstract（参考訳）: 学習者が一連のエピソードにおいてマルコフ決定プロセスと相互作用するオンライン学習問題を考える。そこでは、報酬関数は、敵対的な方法でエピソード間を変更でき、学習者は、その行動に付随する報酬のみを観察できる。
我々は状態空間を任意に大きめにするが、すべてのアクション値関数は既知の低次元特徴写像で線形関数として表現でき、学習者は真のMDP力学から軌道を生成することができる環境シミュレータにアクセスすることができると仮定する。
主な貢献は、mdp-linexp3と呼ばれる計算効率の良いアルゴリズムを開発し、その後悔が$\widetilde{\mathcal{o}}\big(h^2 t^{2/3} (dk)^{1/3}\big)$($t$はエピソード数、$h$は各エピソードのステップ数、$k$はアクション数、$d$はフィーチャーマップの次元であることを示すことです。
また、この後悔は MDP 力学のより強い仮定の下で $\widetilde{\mathcal{O}}\big(H^2 \sqrt{TdK}\big)$ に改善できることを示す。
我々の知る限り、MDP-LinExp3はこの問題設定のための最初の証明可能な効率的なアルゴリズムである。
関連論文リスト
- Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。
非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。
我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear
MDPs If You Learn What to Ignore [0.0]
エピソードマルコフ決定過程(MDP)におけるオンライン強化学習の検討
2つのクラスの違いは、線形に$qpi$-realizable MDPにおける状態の存在であることを示す。
線形$qpi$-realizable MDPのための新しい(計算非効率な)学習アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-10-11T18:50:25Z) - Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles [39.10180309328293]
本稿では,特徴選択の観点から線形MDPを再考する。
我々の主な成果は、この問題に対する最初のアルゴリズムである。
コンベックスプログラミングによって効率よく計算できることを示す。
論文 参考訳（メタデータ） (2023-09-18T03:35:48Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳（メタデータ） (2020-11-23T17:25:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。