Temporal Difference Learning特征演化机制的理论分析
On the Feature Evolution of Temporal Difference Learning
一篇强化学习理论论文，证明了 TD 学习里特征怎么自己长出来，还给出 regret 保证，做 RL 理论的可以看看推导思路。
论文在有限宽度两层 ReLU critic 与平滑随机 horizon-H MDP 家族上研究 TD learning 特征的涌现与传播。结果显示同时更新隐藏权重与输出头相比仅训头的 SGD 有 2(d+1) 倍更大的总体二次响应。通过每份目标样本执行一步 SGD 的耦合更新分析，得到 exp[-Ω(K/(Hd))] 量级的一致预测误差瞬态，无需求解中间 Bellman 回归。在有界奖励的 signed-action MDP 上，exploration-then-commit 算法以 K=Õ(Hd) 次全局更新取得 Õ(d³H^(1/3)T^(2/3)) regret。
On the Feature Evolution of Temporal Difference Learning
Temporal-difference (TD) learning trains neural representations using bootstrapped targets generated by evolving value estimates, yet how predictive features emerge and propagate under incomplete neural updates remains poorly understood. We investigate this problem using finite-width two-layer ReLU critics on a constructed family of smooth stochastic horizon-$H$ MDPs with unknown quadratic structure and $d$-dimensional observations. We first show that an informative TD update acquires the quadratic Bellman signal and yields a representation admitting a bounded predictive readout. The simultaneous hidden-weight and head update achieves a strict finite-sample prediction-risk improvement over matched head-only SGD, with a $2(d+1)$-fold larger population quadratic response. We then establish that an imperfect learned continuation can already provide informative supervision to an earlier zero-reward stage. By tracking coupled neural updates with one SGD step per target copy, without requiring intermediate Bellman regressions to be solved, we obtain a uniform prediction-error transient $\exp[-Ω(K/(Hd))]$, up to action-independent shifts and explicit sampling and finite-width errors. On the constructed signed-action MDP family whose total reward is bounded by 1, we show that an exploration-then-commit algorithm can achieve $\widetilde{O}(d^3H^{1/3}T^{2/3})$ regret over $T$ episodes, using $K=\widetilde{O}(Hd)$ global updates. Our analysis connects bootstrapped feature acquisition, concurrent neural refinement, and finite-budget policy performance.