論文の概要: Convergence of Batch Asynchronous Stochastic Approximation With
Applications to Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2109.03445v1
- Date: Wed, 8 Sep 2021 06:06:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-10 02:02:20.959876
- Title: Convergence of Batch Asynchronous Stochastic Approximation With
Applications to Reinforcement Learning
- Title(参考訳): バッチ非同期確率近似の収束と強化学習への応用
- Authors: Rajeeva L. Karandikar and M. Vidyasagar
- Abstract要約: 凸近似(英: convex approximation、SA)アルゴリズムは、 $mathbff(boldsymboltheta) = mathbf0$ ここで mathbff mathbbRdarrow mathbbRdarrow mathbbRd という形の方程式の解を求めるために広く用いられる確率的手法である。
- 参考スコア(独自算出の注目度): 1.2640278589409006
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The stochastic approximation (SA) algorithm is a widely used probabilistic
method for finding a solution to an equation of the form
$\mathbf{f}(\boldsymbol{\theta}) = \mathbf{0}$ where $\mathbf{f} : \mathbb{R}^d
\rightarrow \mathbb{R}^d$, when only noisy measurements of $\mathbf{f}(\cdot)$
are available. In the literature to date, one can make a distinction between
"synchronous" updating, whereby the entire vector of the current guess
$\boldsymbol{\theta}_t$ is updated at each time, and "asynchronous" updating,
whereby ony one component of $\boldsymbol{\theta}_t$ is updated. In convex and
nonconvex optimization, there is also the notion of "batch" updating, whereby
some but not all components of $\boldsymbol{\theta}_t$ are updated at each time
$t$. In addition, there is also a distinction between using a "local" clock
versus a "global" clock. In the literature to date, convergence proofs when a
local clock is used make the assumption that the measurement noise is an i.i.d\
sequence, an assumption that does not hold in Reinforcement Learning (RL).
In this note, we provide a general theory of convergence for batch
asymchronous stochastic approximation (BASA), that works whether the updates
use a local clock or a global clock, for the case where the measurement noises
form a martingale difference sequence. This is the most general result to date
and encompasses all others.
- Abstract(参考訳): 確率近似(英: stochastic approximation, sa)アルゴリズムは、大雑把な測定値である$\mathbf{f}(\boldsymbol{\theta}) = \mathbf{0}$ where $\mathbf{f} : \mathbb{r}^d \rightarrow \mathbb{r}^d$ の方程式に対する解を見つけるために広く用いられる確率的手法である。
これまでの文献では、現在の推定値$\boldsymbol{\theta}_t$の全ベクトルが更新される「同期」更新と、$\boldsymbol{\theta}_t$の1つのコンポーネントが更新される「同期」更新とを区別することができる。
convex と nonconvex の最適化では、"batch" の更新の概念もあり、$\boldsymbol{\theta}_t$ のすべてのコンポーネントが $t$ のたびに更新されるわけではない。
さらに、"ローカル"クロックと"グローバル"クロックの区別もある。
これまでの文献では、局所クロックを使用する場合の収束証明は、測定ノイズがi.i.d\シーケンスであると仮定しており、これは強化学習(rl)では持たない仮定である。
本稿では,観測ノイズがマルティンゲール差分列を形成する場合において,更新が局所クロックか大域クロックかに関わらず動作するバッチ漸近確率近似 (basa) の収束の一般理論を提案する。
これは今まででもっとも一般的な結果であり、他の全てを包含している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。