論文の概要: Convergence of Batch Asynchronous Stochastic Approximation With
Applications to Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2109.03445v4
- Date: Mon, 3 Apr 2023 08:15:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 02:02:32.786275
- Title: Convergence of Batch Asynchronous Stochastic Approximation With
Applications to Reinforcement Learning
- Title(参考訳): バッチ非同期確率近似の収束と強化学習への応用
- Authors: Rajeeva L. Karandikar and M. Vidyasagar
- Abstract要約: 我々は、そのようなアルゴリズムが研究中の地図の固定点に収束することを証明するための一般的な方法論を開発する。
本稿では、値に対する時間差$TD(lambda)$と、最適なアクション値関数を求めるための$Q$-learningアルゴリズムを分析する。
- 参考スコア(独自算出の注目度): 1.1127149900807178
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The stochastic approximation (SA) algorithm is a widely used probabilistic
method for finding a zero or a fixed point of a vector-valued funtion, when
only noisy measurements of the function are available. In the literature to
date, one makes a distinction between ``synchronous'' updating, whereby every
component of the current guess is updated at each time, and ``asynchronous''
updating, whereby only one component is updated. In this paper, we study an
intermediate situation that we call ``batch asynchronous stochastic
approximation'' (BASA), in which, at each time instant, \textit{some but not
all} components of the current estimated solution are updated. BASA allows the
user to trade off memory requirements against time complexity. We develop a
general methodology for proving that such algorithms converge to the fixed
point of the map under study. These convergence proofs make use of weaker
hypotheses than existing results. Specifically, existing convergence proofs
require that the measurement noise is a zero-mean i.i.d\ sequence or a
martingale difference sequence. In the present paper, we permit biased
measurements, that is, measurement noises that have nonzero conditional mean.
Also, all convergence results to date assume that the stochastic step sizes
satisfy a probabilistic analog of the well-known Robbins-Monro conditions. We
replace this assumption by a purely deterministic condition on the
irreducibility of the underlying Markov processes.
As specific applications to Reinforcement Learning, we analyze the temporal
difference algorithm $TD(\lambda)$ for value iteration, and the $Q$-learning
algorithm for finding the optimal action-value function. In both cases, we
establish the convergence of these algorithms, under milder conditions than in
the existing literature.
- Abstract(参考訳): 確率近似(英: stochastic approximation、SA)アルゴリズムは、関数のノイズ測定のみが利用可能であるとき、ベクトル値の試行の零点または定点を見つけるために広く用いられる確率的手法である。
これまでの文献では、‘synchronous’ の更新と、現在の推測のすべてのコンポーネントが毎回更新される `synchronous'' の更新とを区別し、1つのコンポーネントだけが更新される。
本稿では,現在推定されている解のコンポーネントを瞬時に更新する,‘batch asynchronous stochastic approximation’(basa)と呼ばれる中間状態について検討する。
BASAにより、ユーザーはメモリ要件を時間的複雑さと引き換えることができる。
このようなアルゴリズムが研究中の写像の不動点に収束することを示す一般的な方法を開発した。
これらの収束証明は、既存の結果よりも弱い仮説を用いる。
具体的には、既存の収束証明は、測定ノイズがゼロ平均i.i.d\列またはマルティンゲール差分列である必要がある。
本稿では,非ゼロ条件平均の計測ノイズについて,偏りの測定を許可する。
また、すべての収束結果は、確率的ステップサイズがよく知られたロビンズ・モンロ条件の確率的類似性を満たすと仮定している。
この仮定を,マルコフ過程の既約性に関する純粋決定論的条件に置き換える。
Reinforcement Learning への具体的な応用として、時間差分アルゴリズム $TD(\lambda)$ for value iteration と、最適なアクション値関数を見つけるための $Q$-learning アルゴリズムを解析する。
どちらの場合も、既存の文献よりも穏やかな条件下でこれらのアルゴリズムの収束を確立する。
関連論文リスト
- Convergence Rates for Stochastic Approximation: Biased Noise with
Unbounded Variance, and Applications [2.3134637611088653]
1951年にRobinsとMonroによって導入された近似アルゴリズムは $mathbff(boldsymboltheta) = mathbf0 という形の方程式を解く標準的な方法である。
本稿では,SA理論を拡張し,非ゼロ条件平均および/または条件分散の誤差を包含する。
さらに、収束率の推定を導出し、最適ステップサイズを計算して収束率を最大化する。
論文 参考訳(メタデータ) (2023-12-05T15:22:39Z) - On the Role of Entanglement and Statistics in Learning [3.729242965449096]
我々は,絡み合った,分離可能な,統計的に測定された学習モデルと学習モデルとの関係を理解することを進める。
我々は、QSQ学習と量子学習を交絡測定で指数関数的に分離するクラスC$を示す。
我々は,純度テスト,シャドウトモグラフィ,アベリア隠れ部分群問題,次数2$関数,植込み双斜め状態,クリフォード深度回路の出力状態について,超ポリノミカルQSQの下界を証明した。
論文 参考訳(メタデータ) (2023-06-05T18:16:03Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - Extending Universal Approximation Guarantees: A Theoretical
Justification for the Continuity of Real-World Learning Tasks [0.0]
条件付き期待値によって与えられる学習タスクを、MathrmEleft[Y mid X = xright]$にマップする。
我々は、ランダム化された安定マッチングの例を用いて、条件のリアリズムを動機づける。
論文 参考訳(メタデータ) (2022-12-06T23:33:04Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳(メタデータ) (2022-03-28T23:53:48Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳(メタデータ) (2021-06-15T11:21:06Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳(メタデータ) (2020-12-29T14:06:09Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。