論文の概要: Learning Near Optimal Policies with Low Inherent Bellman Error
- arxiv url: http://arxiv.org/abs/2003.00153v3
- Date: Sun, 28 Jun 2020 23:46:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 20:08:08.637767
- Title: Learning Near Optimal Policies with Low Inherent Bellman Error
- Title（参考訳）: 低固有ベルマン誤差による最適政策に近い学習
- Authors: Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, Emma Brunskill
- Abstract要約: エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
- 参考スコア（独自算出の注目度）: 115.16037976819331
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the exploration problem with approximate linear action-value
functions in episodic reinforcement learning under the notion of low inherent
Bellman error, a condition normally employed to show convergence of approximate
value iteration. First we relate this condition to other common frameworks and
show that it is strictly more general than the low rank (or linear) MDP
assumption of prior work. Second we provide an algorithm with a high
probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H
\sqrt{d_t} \IBE K)$ where $H$ is the horizon, $K$ is the number of episodes,
$\IBE$ is the value if the inherent Bellman error and $d_t$ is the feature
dimension at timestep $t$. In addition, we show that the result is unimprovable
beyond constants and logs by showing a matching lower bound. This has two
important consequences: 1) it shows that exploration is possible using only
\emph{batch assumptions} with an algorithm that achieves the optimal
statistical rate for the setting we consider, which is more general than prior
work on low-rank MDPs 2) the lack of closedness (measured by the inherent
Bellman error) is only amplified by $\sqrt{d_t}$ despite working in the online
setting. Finally, the algorithm reduces to the celebrated \textsc{LinUCB} when
$H=1$ but with a different choice of the exploration parameter that allows
handling misspecified contextual linear bandits. While computational
tractability questions remain open for the MDP setting, this enriches the class
of MDPs with a linear representation for the action-value function where
statistically efficient reinforcement learning is possible.
- Abstract（参考訳）: 近似値反復の収束を示すために通常用いられるベルマン誤差の低い条件の下で, エピソディック強化学習における近似線形作用値関数を用いた探索問題について検討する。
まず、この条件を他の共通フレームワークに関連付け、前処理の低階(または線形)の MDP の仮定よりも厳密に一般化されていることを示す。
次に、$\widetilde o(\sum_{t=1}^h d_t \sqrt{k} + \sum_{t=1}^h \sqrt{d_t} \ibe k)$ ここで$h$は地平線、$k$はエピソード数、$\ibe$は固有のベルマンエラーと$d_t$がタイムステップ$t$の特徴次元である場合の値である。
さらに, 一致した下界を示すことにより, 結果が定数やログを超えないことを示す。
これは2つの重要な結果をもたらす。
1) 低ランクmdpにおける従来の作業よりも一般的である設定の最適統計量を達成するアルゴリズムを用いて, \emph{batch assumptions} のみを用いて探索が可能であることを示す。
2) 閉性(ベルマン誤差によって測定される)の欠如は、オンライン環境での作業にもかかわらず$\sqrt{d_t}$でのみ増幅される。
最後に、このアルゴリズムは、$H=1$のときの有名な \textsc{LinUCB} に還元されるが、不特定コンテキスト線形帯域を扱うことができる探索パラメータの異なる選択を持つ。
MDPの設定には計算的トラクタビリティの問題がまだ残っているが、これは統計的に効率的な強化学習が可能なアクション値関数の線形表現でMDPのクラスを豊かにする。
関連論文リスト
- The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation [29.69428894587431]
本稿では,線形関数近似を用いたオフラインRL問題について検討する。
我々の構造的前提は、MDPはベルマン誤差が低いということである。
我々は、$sqrtvarepsilon_mathrmBE$によるサブ最適性のスケーリングは、どんなアルゴリズムでも改善できないことを示した。
論文 参考訳（メタデータ） (2024-06-17T16:04:06Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。
提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文 参考訳（メタデータ） (2023-10-23T18:52:17Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-22T03:20:40Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。