論文の概要: Distances for Markov chains from sample streams

• arxiv url: http://arxiv.org/abs/2505.18005v1
• Date: Fri, 23 May 2025 15:09:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:34.181823
• Title: Distances for Markov chains from sample streams
• Title（参考訳）: サンプルストリームからのマルコフ鎖の距離
• Authors: Sergio Calo, Anders Jonsson, Gergely Neu, Ludovic Schwartz, Javier Segovia-Aguas,
• Abstract要約: シミュレーションメトリクスは、プロセス間の類似性、特にマルコフ連鎖を測定する強力なツールである。 近年の進歩により、バイシミュレーションのメトリクスは、実際、最適な輸送距離であり、証明可能な精度と実行時の保証で、そのようなメトリクスを計算するための高速なアルゴリズムの開発を可能にしていることが判明した。 これは多くの場合、ほとんどの実世界のシナリオでは非現実的な仮定であり、典型的にはサンプル軌道のみが利用可能である。 本稿では,この制限に対処する新しい最適化手法を提案し,サンプルアクセスに基づくバイシミュレーションのメトリクスを,明示的な遷移モデルを必要とせずに推定する。
• 参考スコア（独自算出の注目度）: 16.443304244634767
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bisimulation metrics are powerful tools for measuring similarities between stochastic processes, and specifically Markov chains. Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees. However, these recent methods, as well as all previously known methods, assume full knowledge of the transition dynamics. This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available. In this work, we propose a stochastic optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models. Our approach is derived from a new linear programming (LP) formulation of bisimulation metrics, which we solve using a stochastic primal-dual optimization method. We provide theoretical guarantees on the sample complexity of the algorithm and validate its effectiveness through a series of empirical evaluations.
• Abstract（参考訳）: ビシミュレーションメトリクスは確率過程、特にマルコフ連鎖の類似性を測定する強力なツールである。 近年の進歩により、バイシミュレーションのメトリクスは、実際、最適な輸送距離であり、証明可能な精度と実行時の保証で、そのようなメトリクスを計算するための高速なアルゴリズムの開発を可能にしていることが判明した。 しかしながら、これらの最近の手法は、以前にも知られていたすべての方法と同様に、遷移力学の完全な知識を前提としている。 これは多くの場合、ほとんどの実世界のシナリオでは非現実的な仮定であり、典型的にはサンプル軌道のみが利用可能である。 本研究では,この制限に対処する確率的最適化手法を提案し,サンプルアクセスに基づくシミュレーションのメトリクスを,明示的な遷移モデルを必要とせずに推定する。 提案手法は,確率的原始双対最適化法を用いて解いた2次元数値の線形計画法(LP)から導かれる。 我々は,アルゴリズムのサンプル複雑性に関する理論的保証を提供し,一連の経験的評価を通じてその有効性を検証する。

関連論文リスト

• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• The Stochastic Proximal Distance Algorithm [5.3315823983402755]
  本稿では,所望の制約付き推定問題をペナルティパラメータとして回復する反復最適化手法のクラスを提案し,解析する。 我々は、最近の理論装置を拡張して有限誤差境界を確立し、収束率の完全な評価を行う。 また,本手法が一般的な学習課題のバッチバージョンより優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T22:07:28Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling [0.9806910643086042]
  本稿では,勾配降下アルゴリズムの平均化法により推定されるパラメータのベクトルに対するオンライン推論法を提案する。 我々のアプローチはオンラインデータで完全に運用されており、機能中心極限定理によって厳格に支えられている。
  論文  参考訳（メタデータ） (2021-06-06T15:38:37Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization [18.259478519717426]
  本稿では、同時局所化およびマッピング(SLAM)におけるマップ間ループ閉包外乱検出のための、新しい分散手法を提案する。 提案アルゴリズムは優れた初期化に頼らず、一度に2つ以上のマップを処理できる。
  論文  参考訳（メタデータ） (2020-02-07T06:34:44Z)

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

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