論文の概要: Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency

• arxiv url: http://arxiv.org/abs/2302.10371v1
• Date: Tue, 21 Feb 2023 00:17:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-22 16:54:15.580546
• Title: Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency
• Title（参考訳）: 線形帯域と強化学習のための変数依存回帰境界:適応性と計算効率
• Authors: Heyang Zhao and Jiafan He and Dongruo Zhou and Tong Zhang and Quanquan Gu
• Abstract要約: 本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 90.40062452292091
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, several studies (Zhou et al., 2021a; Zhang et al., 2021b; Kim et al., 2021; Zhou and Gu, 2022) have provided variance-dependent regret bounds for linear contextual bandits, which interpolates the regret for the worst-case regime and the deterministic reward regime. However, these algorithms are either computationally intractable or unable to handle unknown variance of the noise. In this paper, we present a novel solution to this open problem by proposing the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $\tilde{O}(d \sqrt{\sum_{k = 1}^K \sigma_k^2} + d)$ regret, where $\sigma_k^2$ is the variance of the noise at the round $k$, $d$ is the dimension of the contexts and $K$ is the total number of rounds. Our results are based on an adaptive variance-aware confidence set enabled by a new Freedman-type concentration inequality for self-normalized martingales and a multi-layer structure to stratify the context vectors into different layers with different uniform upper bounds on the uncertainty. Furthermore, our approach can be extended to linear mixture Markov decision processes (MDPs) in reinforcement learning. We propose a variance-adaptive algorithm for linear mixture MDPs, which achieves a problem-dependent horizon-free regret bound that can gracefully reduce to a nearly constant regret for deterministic MDPs. Unlike existing nearly minimax optimal algorithms for linear mixture MDPs, our algorithm does not require explicit variance estimation of the transitional probabilities or the use of high-order moment estimators to attain horizon-free regret. We believe the techniques developed in this paper can have independent value for general online decision making problems.
• Abstract（参考訳）: 近年、いくつかの研究 (Zhou et al., 2021a; Zhang et al., 2021b; Kim et al., 2021; Zhou and Gu, 2022) が、線形文脈的包帯に対する変分依存的後悔境界を提供しており、最悪のケース体制と決定論的報酬体制の後悔を補間している。 しかし、これらのアルゴリズムは計算が難しいか、ノイズの未知のばらつきを処理できないかのどちらかである。 本稿では,ヘテロシドスティックノイズを持つ線形バンディットに対して,最初の計算効率の高いアルゴリズムを提案することにより,この問題に対する新しい解法を提案する。 このアルゴリズムは未知のノイズ分散に適応し、$\tilde{o}(d \sqrt{\sum_{k = 1}^k \sigma_k^2} + d)$ regret(ここで$\sigma_k^2$はラウンド$k$のノイズ分散、$d$はコンテキストの次元、$k$はラウンドの総数)を達成する。 本研究は, 自己正規化マルチンゲールに対する新しいフリードマン型濃度不等式と, 不確実性上界が異なる異なる層にコンテキストベクトルを階層化するための多層構造によって実現される適応分散認識信頼セットに基づいている。 さらに,本手法は強化学習において線形混合マルコフ決定過程(MDP)に拡張することができる。 本稿では,線形混合型MDPに対する分散適応アルゴリズムを提案する。 線形混合 MDP に対する既存の極小近似アルゴリズムとは異なり、我々のアルゴリズムは過渡確率の明示的な分散推定や高次モーメント推定器を用いることで、地平線無しの後悔を実現する。 本論文で開発された手法は,一般的なオンライン意思決定問題に対して独立した価値を持つことができると考えている。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
  プレイヤーが$d$ベースアイテムを含むセットのパワーセットから$P$アクションの中から選択する半帯域の問題に対処する。 提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-23T08:07:54Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds [27.92755687977196]
  本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。 高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。 提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
  論文  参考訳（メタデータ） (2023-02-24T00:02:24Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。 環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。 モデルに基づく手法では、MVPアルゴリズムの変種を設計する。 特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
  論文  参考訳（メタデータ） (2023-01-31T06:54:06Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。