論文の概要: Markov Chain Variance Estimation: A Stochastic Approximation Approach
- arxiv url: http://arxiv.org/abs/2409.05733v1
- Date: Mon, 9 Sep 2024 15:42:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-10 14:06:46.361019
- Title: Markov Chain Variance Estimation: A Stochastic Approximation Approach
- Title(参考訳): マルコフ連鎖変動推定法 : 確率近似法
- Authors: Shubhada Agrawal, Prashanth L. A., Siva Theja Maguluri,
- Abstract要約: マルコフ連鎖上で定義された関数の計算分散を推定する問題を考える。
我々は、各ステップで$O(1)$の保存を必要とする最初の再帰的推定器を設計する。
平均報酬強化学習における推定器の応用について述べる。
- 参考スコア(独自算出の注目度): 14.883782513177094
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of estimating the asymptotic variance of a function defined on a Markov chain, an important step for statistical inference of the stationary mean. We design the first recursive estimator that requires $O(1)$ computation at each step, does not require storing any historical samples or any prior knowledge of run-length, and has optimal $O(\frac{1}{n})$ rate of convergence for the mean-squared error (MSE) with provable finite sample guarantees. Here, $n$ refers to the total number of samples generated. The previously best-known rate of convergence in MSE was $O(\frac{\log n}{n})$, achieved by jackknifed estimators, which also do not enjoy these other desirable properties. Our estimator is based on linear stochastic approximation of an equivalent formulation of the asymptotic variance in terms of the solution of the Poisson equation. We generalize our estimator in several directions, including estimating the covariance matrix for vector-valued functions, estimating the stationary variance of a Markov chain, and approximately estimating the asymptotic variance in settings where the state space of the underlying Markov chain is large. We also show applications of our estimator in average reward reinforcement learning (RL), where we work with asymptotic variance as a risk measure to model safety-critical applications. We design a temporal-difference type algorithm tailored for policy evaluation in this context. We consider both the tabular and linear function approximation settings. Our work paves the way for developing actor-critic style algorithms for variance-constrained RL.
- Abstract(参考訳): マルコフ連鎖上で定義される関数の漸近的分散を推定する問題は、定常平均の統計的推測の重要なステップである。
我々は各ステップで$O(1)$計算を必要とする最初の再帰的推定器を設計し、履歴サンプルやラン長に関する事前知識を保存する必要がなく、証明可能な有限標本保証付き平均二乗誤差(MSE)に対する最適$O(\frac{1}{n})$収束率を持つ。
ここで、$n$は生成されたサンプルの総数を指す。
以前はMSEの収束率が最もよく知られていたのは、ジャックニフ付き推定器によって達成された$O(\frac{\log n}{n})$であり、これら他の望ましい性質も享受していない。
我々の推定子は、ポアソン方程式の解の項による漸近分散の等価な定式化の線形確率近似に基づいている。
我々は,ベクトル値関数の共分散行列の推定,マルコフ鎖の定常分散の推定,および基礎となるマルコフ鎖の状態空間が大きくなるような条件下での漸近分散の推定など,いくつかの方向の近似器を一般化する。
また, 平均報酬強化学習(RL)における推定器の応用について述べる。
この文脈でポリシー評価に適した時間差型アルゴリズムを設計する。
表型および線形関数近似の設定について検討する。
我々の研究は、分散制約付きRLのためのアクター・クリティカルなスタイルのアルゴリズムを開発するための道を開いた。
関連論文リスト
- Online covariance estimation for stochastic gradient descent under
Markovian sampling [20.02012768403544]
位数$Obig(sqrtd,n-1/8(log n)1/4big)$の収束率は、状態依存および状態依存マルコフサンプリングの下で確立される。
本手法はロジスティック回帰を用いた戦略分類に適用され, 学習中の特徴を適応的に修正し, 対象クラス分類に影響を与える。
論文 参考訳(メタデータ) (2023-08-03T00:21:30Z) - Covariance Estimators for the ROOT-SGD Algorithm in Online Learning [7.00422423634143]
ROOT-SGDのアルゴリズム共分散に対する2つの推定器を開発した。
最初の推定器はプラグインの考え方を採用し, 共分散公式の未知の要素ごとに, 経験的手法で置き換える。
2つ目の推定器は、制限を克服するヘッセン自由推定器である。
論文 参考訳(メタデータ) (2022-12-02T15:55:52Z) - Policy evaluation from a single path: Multi-step methods, mixing and
mis-specification [45.88067550131531]
無限水平$gamma$-discounted Markov rewardプロセスの値関数の非パラメトリック推定について検討した。
カーネルベースの多段階時間差推定の一般的なファミリーに対して、漸近的でない保証を提供する。
論文 参考訳(メタデータ) (2022-11-07T23:15:25Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳(メタデータ) (2022-01-21T02:46:57Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。
本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文 参考訳(メタデータ) (2020-06-13T06:09:27Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z) - Communication-Efficient Distributed Estimator for Generalized Linear
Models with a Diverging Number of Covariates [7.427903819459701]
2ラウンドの通信により,大規模分散データに対する効率の良い推定器を得る手法が提案されている。
本手法では,サーバ数に対する仮定をより緩和し,現実のアプリケーションに対して実用的である。
論文 参考訳(メタデータ) (2020-01-17T08:51:11Z) - Statistical Inference for Model Parameters in Stochastic Gradient
Descent [45.29532403359099]
勾配降下係数(SGD)は,その計算効率とメモリ効率から,大規模データの統計的推定に広く用いられている。
人口減少関数が強い凸であり,一定の条件を満たす場合,SGDに基づく真のモデルパラメータの統計的推測の問題について検討する。
論文 参考訳(メタデータ) (2016-10-27T07:04:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。