論文の概要: Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning
- arxiv url: http://arxiv.org/abs/2106.14352v1
- Date: Mon, 28 Jun 2021 00:38:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-30 01:00:52.683942
- Title: Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning
- Title（参考訳）: 最適値推定におけるインスタンス最適性:分散還元q-learningによる適応性
- Authors: Koulik Khamaru, Eric Xia, Martin J. Wainwright, and Michael I. Jordan
- Abstract要約: 本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
- 参考スコア（独自算出の注目度）: 99.34907092347733
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Various algorithms in reinforcement learning exhibit dramatic variability in
their convergence rates and ultimate accuracy as a function of the problem
structure. Such instance-specific behavior is not captured by existing global
minimax bounds, which are worst-case in nature. We analyze the problem of
estimating optimal $Q$-value functions for a discounted Markov decision process
with discrete states and actions and identify an instance-dependent functional
that controls the difficulty of estimation in the $\ell_\infty$-norm. Using a
local minimax framework, we show that this functional arises in lower bounds on
the accuracy on any estimation procedure. In the other direction, we establish
the sharpness of our lower bounds, up to factors logarithmic in the state and
action spaces, by analyzing a variance-reduced version of $Q$-learning. Our
theory provides a precise way of distinguishing "easy" problems from "hard"
ones in the context of $Q$-learning, as illustrated by an ensemble with a
continuum of difficulty.
- Abstract（参考訳）: 強化学習における様々なアルゴリズムは、その収束率と最終的な精度を問題構造の関数として劇的な変動を示す。
このようなインスタンス固有の振る舞いは、本質的に最悪の場合である既存のグローバルミニマックス境界では捉えられません。
割引マルコフ決定過程に対する最適な$Q$値関数を離散状態と動作で推定する問題を解析し、$\ell_\infty$-normにおける推定の困難さを制御するインスタンス依存関数を同定する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方では、分散削減された$q$-learningの版を分析して、状態と行動空間における対数的な要因まで、下限の鋭さを確立する。
本理論は,難易度が連続するアンサンブルによって示されるように,q$-learningの文脈で「簡単な」問題を「ハード」な問題と区別する正確な方法を提供する。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis [2.1756081703276]
凸制約下での凸最適化のための自然分散低減近位勾配(VRPG)アルゴリズムの挙動を解析する。
我々の主な成果は、VRPGアルゴリズムの漸近的でない保証である。
我々の保証は、損失関数の複雑さ、雑音の可変性、制約集合の幾何を捉えていることを示す。
論文 参考訳（メタデータ） (2024-03-24T14:45:11Z) - Improved Sample Complexity Bounds for Distributionally Robust
Reinforcement Learning [3.222802562733787]
トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。
本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。
提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
論文 参考訳（メタデータ） (2023-03-05T21:47:08Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-14T21:54:31Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - Isotonic regression with unknown permutations: Statistics, computation,
and adaptation [13.96377843988598]
我々は、推定のミニマックスリスク(実証的な$L$損失)と適応の基本的な限界(適応度指数で定式化)について検討する。
バニラ時間プロシージャで可能な最小適応率を達成しつつ、最小限の最適化が可能なミルスキー分割推定器を提供する。
相補的な方向において、既存の推定器の自然な修正は、デシデラタの最適統計性能、計算効率、高速適応の少なくとも1つを満たすことができないことを示す。
論文 参考訳（メタデータ） (2020-09-05T22:17:51Z) - Relative Pose Estimation of Calibrated Cameras with Known
$\mathrm{SE}(3)$ Invariants [65.2314683780204]
既知の$mathrmSE(3)$不変量で制約されたカメラの相対ポーズ推定問題について完全な研究を行う。
これらの問題は、相対的なポーズ推定のための点対の最小数を減少させる。
合成データと実データを用いた実験では,従来の相対ポーズ推定法と比較して性能が向上した。
論文 参考訳（メタデータ） (2020-07-15T13:55:55Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。