論文の概要: Asymptotically Optimal Sequential Testing with Markovian Data

• arxiv url: http://arxiv.org/abs/2602.17587v1
• Date: Thu, 19 Feb 2026 18:11:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-20 15:21:29.289119
• Title: Asymptotically Optimal Sequential Testing with Markovian Data
• Title（参考訳）: マルコフデータを用いた漸近的最適シーケンステスト
• Authors: Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, P. N. Karthik,
• Abstract要約: 我々は,エルゴディックマルコフ連鎖によって生成されるデータに対して,一側および$$-correct sequence hypothesis testについて検討した。 我々は,有効なシーケンシャルテストの停止時間に対して,非漸近性に依存しない厳密なインスタンスを確立する。 本研究はマルコフ依存下での最適シーケンシャルテスト手順の鋭く一般的な特徴である。
• 参考スコア（独自算出の注目度）: 20.18233038746029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study one-sided and $α$-correct sequential hypothesis testing for data generated by an ergodic Markov chain. The null hypothesis is that the unknown transition matrix belongs to a prescribed set $P$ of stochastic matrices, and the alternative corresponds to a disjoint set $Q$. We establish a tight non-asymptotic instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative. Our novel analysis improves the existing lower bounds, which are either asymptotic or provably sub-optimal in this setting. Our lower bound incorporates both the stationary distribution and the transition structure induced by the unknown Markov chain. We further propose an optimal test whose expected stopping time matches this lower bound asymptotically as $α\to 0$. We illustrate the usefulness of our framework through applications to sequential detection of model misspecification in Markov Chain Monte Carlo and to testing structural properties, such as the linearity of transition dynamics, in Markov decision processes. Our findings yield a sharp and general characterization of optimal sequential testing procedures under Markovian dependence.
• Abstract（参考訳）: エルゴディックマルコフ連鎖が生成するデータに対して,一側およびα$の逐次仮説を検証した。 ヌル仮説は、未知遷移行列が所定集合$P$の確率行列に属し、その代替は非連結集合$Q$に対応するというものである。 我々は、その代替となる有効なシーケンシャルテストの期待停止時間に基づいて、漸近的でないインスタンス依存の下限を厳密に設定する。 我々の新しい分析は、この設定において、漸近的または証明可能な準最適である既存の下界を改善する。 我々の下界は、未知のマルコフ鎖によって誘導される定常分布と遷移構造の両方を包含する。 さらに、この下界が漸近的に$α\to 0$と一致すると予測された停止時間が一致する最適試験を提案する。 マルコフ・チェイン・モンテカルロにおけるモデル不特定の逐次検出や、マルコフ決定過程における遷移力学の線形性などの構造的特性の試験への応用を通して、我々のフレームワークの有用性を説明する。 本研究はマルコフ依存下での最適シーケンシャルテスト手順の鋭く一般的な特徴である。

関連論文リスト

• Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks [11.3631620309434]
  エージェントのネットワークをランダムウォーク方式で横断するトークンによって勾配をサンプリングする分散最適化アルゴリズムの一群について検討する。 我々は、正則線型マルコフトークンを非線形マルコフ連鎖、すなわち自己推進ラドムウォーク(SRRW)に従うものに置き換えることで、新しいアプローチをとる。 結果のSA-SRRWの最適化誤差はほぼ確実にゼロに収束し、中心極限定理を証明する。
  論文  参考訳（メタデータ） (2024-01-18T00:50:37Z)
• Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
  マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。 ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。 我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
  論文  参考訳（メタデータ） (2023-12-07T14:09:27Z)
• Testing for the Markov Property in Time Series via Deep Conditional Generative Learning [6.7826352751791985]
  本研究では,高次元時系列におけるマルコフ特性の非パラメトリックテストを提案する。 テストは型Iを誤って制御し、出力が近づいていることを示します。 非パラメトリック推定を用いるが、パラメトリック収束率を達成する2つの頑健なテスト統計を導出する。
  論文  参考訳（メタデータ） (2023-05-30T17:32:00Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  我々は、一般的な非データ生成プロセスの下で、最初のタイプIエラーと予測リジェクション時間保証を提供する。 本研究では, 平均処理効果など, 方程式を推定することによって定義されるパラメータの推測に, 結果を適用する方法を示す。
  論文  参考訳（メタデータ） (2022-12-29T18:37:08Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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