論文の概要: Improved Regret Analysis for Variance-Adaptive Linear Bandits and
Horizon-Free Linear Mixture MDPs
- arxiv url: http://arxiv.org/abs/2111.03289v1
- Date: Fri, 5 Nov 2021 06:47:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-08 15:12:44.042904
- Title: Improved Regret Analysis for Variance-Adaptive Linear Bandits and
Horizon-Free Linear Mixture MDPs
- Title（参考訳）: 可変適応線形帯域と水平自由線形混合MDPのレギュレット解析の改善
- Authors: Yeoneung Kim, Insoon Yang, Kwang-Sung Jun
- Abstract要約: オンライン学習問題では,低分散の活用がパフォーマンス保証の厳密化に重要な役割を果たしている。
本研究は, 後悔の限界を著しく改善する新たな分析法を提案する。
我々の分析は、新しい楕円型ポテンシャル数補題に依存している。
- 参考スコア（独自算出の注目度）: 12.450760567361531
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In online learning problems, exploiting low variance plays an important role
in obtaining tight performance guarantees yet is challenging because variances
are often not known a priori. Recently, a considerable progress has been made
by Zhang et al. (2021) where they obtain a variance-adaptive regret bound for
linear bandits without knowledge of the variances and a horizon-free regret
bound for linear mixture Markov decision processes (MDPs). In this paper, we
present novel analyses that improve their regret bounds significantly. For
linear bandits, we achieve $\tilde O(d^{1.5}\sqrt{\sum_{k}^K \sigma_k^2} +
d^2)$ where $d$ is the dimension of the features, $K$ is the time horizon, and
$\sigma_k^2$ is the noise variance at time step $k$, and $\tilde O$ ignores
polylogarithmic dependence, which is a factor of $d^3$ improvement. For linear
mixture MDPs, we achieve a horizon-free regret bound of $\tilde
O(d^{1.5}\sqrt{K} + d^3)$ where $d$ is the number of base models and $K$ is the
number of episodes. This is a factor of $d^3$ improvement in the leading term
and $d^6$ in the lower order term. Our analysis critically relies on a novel
elliptical potential `count' lemma. This lemma allows a peeling-based regret
analysis, which can be of independent interest.
- Abstract（参考訳）: オンライン学習問題において、低分散の活用は、厳密なパフォーマンス保証を得る上で重要な役割を果たすが、分散が優先事項として知られていない場合が多いため、難しい。
最近では Zhang et al. (2021) によって、分散の知識のない線形包帯に対する分散適応的後悔境界と、線形混合マルコフ決定過程(MDPs)に対する水平自由な後悔境界が得られている。
本稿では,その後悔関係を著しく改善する新しい分析法を提案する。
線形包帯に対して、$\tilde O(d^{1.5}\sqrt{\sum_{k}^K \sigma_k^2} + d^2)$ ここで、$d$は特徴の次元、$K$は時間軸、$\sigma_k^2$は時間ステップのノイズ分散、$\tilde O$はポリログ依存を無視し、$d^3$の改善の要因である。
線形混合mdpの場合、$d$ は基本モデル数、$k$ はエピソード数、$\tilde o(d^{1.5}\sqrt{k} + d^3)$ となる。
これは、先行項で$d^3$改善、下位項で$d^6$改善の係数である。
我々の分析は、新しい楕円ポテンシャル ‘count' 補題に批判的に依存している。
この補題は剥がしに基づく後悔の分析を可能にし、独立した関心を持つことができる。
関連論文リスト
- 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-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - 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) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - On Frequentist Regret of Linear Thompson Sampling [8.071506311915398]
本稿では,決定者側が $mathbbRd$ の時間依存ベクトル集合から行動を選択し,雑音の報奨を受ける線形帯域問題について検討する。
目的は、後悔を最小限に抑えることであり、決定者の累積的な報奨と、各アクションの期待報奨にアクセスできる神託の報奨とを、一連のT$決定に比較して区別することである。
論文 参考訳（メタデータ） (2020-06-11T20:19:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。