論文の概要: Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP
- arxiv url: http://arxiv.org/abs/2101.12745v2
- Date: Fri, 19 Feb 2021 15:46:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 00:27:30.287143
- Title: Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP
- Title（参考訳）: 可変認識信頼セット:線形帯域に対する可変依存境界と線形混合MDPにおける水平自由境界
- Authors: Zihan Zhang, Jiaqi Yang, Xiangyang Ji, Simon S. Du
- Abstract要約: 線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
- 参考スコア（独自算出の注目度）: 76.94328400919836
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show how to construct variance-aware confidence sets for linear bandits
and linear mixture Markov Decision Process (MDP). Our method yields the
following new regret bounds:
* For linear bandits, we obtain an $\widetilde{O}(\mathrm{poly}(d)\sqrt{1 +
\sum_{i=1}^{K}\sigma_i^2})$ regret bound, where $d$ is the feature dimension,
$K$ is the number of rounds, and $\sigma_i^2$ is the (unknown) variance of the
reward at the $i$-th round. This is the first regret bound that only scales
with the variance and the dimension, with no explicit polynomial dependency on
$K$.
* For linear mixture MDP, we obtain an $\widetilde{O}(\mathrm{poly}(d, \log
H)\sqrt{K})$ regret bound, where $d$ is the number of base models, $K$ is the
number of episodes, and $H$ is the planning horizon. This is the first regret
bound that only scales logarithmically with $H$ in the reinforcement learning
with linear function approximation setting, thus exponentially improving
existing results.
Our methods utilize three novel ideas that may be of independent interest: 1)
applications of the peeling techniques to the norm of input and the magnitude
of variance, 2) a recursion-based approach to estimate the variance, and 3) a
convex potential lemma that somewhat generalizes the seminal elliptical
potential lemma.
- Abstract（参考訳）: 本稿では,線形バンドイットと線形混合マルコフ決定過程(mdp)に対する分散認識信頼集合の構成法を示す。
線形包帯の場合、$\widetilde{O}(\mathrm{poly}(d)\sqrt{1 + \sum_{i=1}^{K}\sigma_i^2})$ regret bound, where $d$ is the feature dimension, $K$ is the number of rounds, $\sigma_i^2$ is the (unknown) variance of the reward at the $i-th round。
これは、$K$に明示的な多項式依存を持たず、分散と次元でしかスケールしない最初の後悔境界である。
* 線形混合 mdp に対して、$\widetilde{o}(\mathrm{poly}(d, \log h)\sqrt{k})$ regret bound、ただし$d$ は基本モデルの数、$k$ はエピソード数、$h$ は計画地平線である。
これは、線形関数近似設定による強化学習でh$で対数的にしかスケールしない最初の後悔の限界であり、既存の結果が指数関数的に改善される。
本手法は, 1 入力のノルムと分散の大きさに対する剥離法の適用, 2) 分散を推定するための再帰的アプローチ, 3) 半楕円的ポテンシャル補題を幾分一般化した凸ポテンシャル補題の3つの新しいアイデアを用いる。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Variance-aware robust reinforcement learning with linear function
approximation with heavy-tailed rewards [6.932056534450556]
AdaOFUL と VARA という2つのアルゴリズムを,重み付き報酬の存在下でのオンラインシーケンシャルな意思決定のために提案する。
AdaOFULは、$widetildemathcalObigの最先端の後悔境界を達成する。
VarA は $widetildemathcalO(dsqrtHmathcalG*K)$ のより厳密な分散を考慮した後悔境界を達成する。
論文 参考訳（メタデータ） (2023-03-09T22:16:28Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Improved Regret Analysis for Variance-Adaptive Linear Bandits and
Horizon-Free Linear Mixture MDPs [12.450760567361531]
オンライン学習問題では,低分散の活用がパフォーマンス保証の厳密化に重要な役割を果たしている。
本研究は, 後悔の限界を著しく改善する新たな分析法を提案する。
我々の分析は、新しい楕円型ポテンシャル数補題に依存している。
論文 参考訳（メタデータ） (2021-11-05T06:47:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。