マルコフ線形確率近似の最適かつ事例依存の保証

私たちは、エルゴードマルコフ連鎖からの長さnの軌跡を観察に基づいて、d次元線形固定点方程式を近似的に解くための確率近似手順を研究します。まず、標準的な手法の最後の反復の二乗誤差に対する非漸近的な上限t₌₈ₗdnを示します。ここで、t₌₈ₗは混合時間です。次に、適切に平均化された反復の系列に対する非漸近的な事例依存の境界を証明し、主項が局所漸近ミニマックス限界と一致し、高次項におけるパラメータ(d, t₌₈ₗ)への鋭い依存性を含みます。私たちは、平均化されたSA推定量の事例最適性を確立する非漸近的ミニマックス下限でこれらの上限を補完します。これらの結果のコロラリーをマルコフノイズを伴うポリシー評価のために導出します—[0, 1)の全てのTD()アルゴリズムファミリーをカバーし、線形自己回帰モデルにも適用されます。私たちの事例依存の特性は、ハイパーパラメータ調整のための詳細なモデル選択手順の設計への扉を開きます（例：TD()アルゴリズムを実行する際のの値を選択すること）。