引言 / Introduction
This chapter begins our study of function approximation in reinforcement learning. The approximate value function is represented not as a table but as a parameterized functional form with weight vector w ∈ ℝd. We write v̂(s,w) ≈ vπ(s). Typically, the number of weights is much less than the number of states (d ≪ |S|), so changing one weight changes the estimated value of many states — such generalization makes learning potentially more powerful but also more difficult.
本章开始研究强化学习中的函数近似。近似价值函数不再用表格表示，而是用带有权重向量w∈ℝd的参数化函数形式表示。我们记v̂(s,w)≈vπ(s)。通常权重的数量远少于状态数（d≪|S|），改变一个权重会影响许多状态的估计值——这种泛化使学习更强大但也更难管理。
Perhaps surprisingly, extending RL to function approximation also makes it applicable to partially observable problems, in which the full state is not available to the agent. If v̂ does not allow the estimate to depend on certain aspects of the state, it is as if those aspects are unobservable.
也许令人惊讶的是，将RL扩展到函数近似也使其适用于部分可观测问题，即智能体无法获得完整状态的情况。如果v̂的估计不依赖于状态的某些方面，那么这些方面就好像是不可观测的。
9.2 预测目标 VE / The Prediction Objective
With function approximation, we cannot get all state values exactly correct. We must specify a state distribution µ(s) ≥ 0 representing how much we care about the error in each state. This yields the Mean Squared Value Error:
在函数近似下，无法让所有状态值完全正确。必须指定一个状态分布µ(s)≥0来表示我们对每个状态误差的关注程度。由此得到均方价值误差：
VE(w) = Σs∈S µ(s) [vπ(s) − v̂(s,w)]2
Often µ(s) is chosen to be the fraction of time spent in s — the on-policy distribution. In continuing tasks, this is the stationary distribution under π. In episodic tasks, it depends on both the initial-state distribution h(s) and the expected number of visits η(s).
通常µ(s)选为在s中停留的时间比例——即on-policy分布。在持续性任务中，这是π下的平稳分布。在回合制任务中，它取决于初始状态分布h(s)和期望访问次数η(s)。
The ideal goal would be to find a global optimum w* for which VE(w*) ≤ VE(w) for all w. This is sometimes possible for linear approximators, but rarely for complex ones like ANNs. Short of this, complex approximators seek a local optimum. Some methods may even diverge, with VE approaching infinity.
理想目标是找到全局最优w*使得对所有w都有VE(w*)≤VE(w)。线性近似器有时可以做到，但神经网络等复杂近似器很少能做到。退而求其次，复杂近似器追求局部最优。一些方法甚至可能发散，VE趋向无穷大。
9.3 随机梯度与半梯度方法 / SGD & Semi-gradient Methods
Stochastic Gradient Descent (SGD) adjusts the weight vector after each example by a small amount in the direction that most reduces the error on that example:
随机梯度下降（SGD）在每次样本之后，沿最快速减少该样本误差的方向调整权重向量一小步：
wt+1 = wt + α [Ut − v̂(St,wt)] ∇v̂(St,wt)
If Ut is an unbiased estimate of vπ(St) (e.g., Gt from Monte Carlo), then SGD converges to a local optimum under standard conditions.
如果Ut是vπ(St)的无偏估计（如MC的Gt），则SGD在标准条件下收敛到局部最优。
Gradient Monte Carlo Algorithm for Estimating v̂ ≈ vπ
────────────────────────────────────────────
Input: the policy π to be evaluated
Input: a differentiable function v̂: S × ℝd → ℝ
Algorithm parameter: step size α > 0
Initialize weights w ∈ ℝd arbitrarily (e.g., w = 0)
Loop forever (for each episode):
Generate episode S₀, A₀, R₁, ..., RT, ST using π
Loop for each step t = 0, 1, ..., T−1:
w ← w + α [Gt − v̂(St, w)] ∇v̂(St, w)
Bootstrapping targets such as Gt:t+n or DP targets depend on wt, making them biased. They include only part of the gradient, so we call them semi-gradient methods. Though less robust in convergence, they offer: (1) significantly faster learning, and (2) continual online learning without waiting for episode end.
自举目标如Gt:t+n或DP目标依赖于wt，使其具有偏差。它们只包含部分梯度，因此称为半梯度方法。虽然收敛性不够鲁棒，但它们具有：(1)显著更快的学习，(2)无需等待回合结束的持续在线学习。
Semi-gradient TD(0) for Estimating v̂ ≈ vπ
────────────────────────────────────────────
Input: policy π to be evaluated
Input: differentiable function v̂: S+ × ℝd → ℝ, v̂(terminal,·) = 0
Algorithm parameter: step size α > 0
Initialize weights w arbitrarily (e.g., w = 0)
Loop for each episode:
Initialize S
Loop for each step:
Choose A ~ π(·|S)
Take action A, observe R, S'
w ← w + α [R + γv̂(S', w) − v̂(S, w)] ∇v̂(S, w)
S ← S'
until S is terminal
Example 9.1: State Aggregation on 1000-state Random Walk. 1000 states are partitioned into 10 groups of 100 states each. State aggregation is a special case of SGD where the gradient is 1 for St's group component and 0 for others. The learned values show a staircase pattern — constant within each group, changing abruptly between groups.
例9.1：1000状态随机游走上的状态聚合。1000个状态被划分为10组，每组100个状态。状态聚合是SGD的特例，梯度在St所在组的分量为1，其他为0。学到的值呈阶梯模式——组内恒定，组间突变。
9.4 线性方法 / Linear Methods
The approximate function is a linear function of the weight vector. For each state s, there is a feature vector x(s) = (x1(s), ..., xd(s))T:
近似函数是权重向量的线性函数。对于每个状态s，有一个特征向量x(s)=(x1(s),...,xd(s))T：
v̂(s,w) = wTx(s) = Σi=1d wi xi(s)
The gradient simplifies to ∇v̂(s,w) = x(s), giving the simple SGD update: wt+1 = wt + α[Ut − v̂(St,wt)]x(St). In the linear case there is only one optimum, so convergence to the global optimum is guaranteed.
梯度简化为∇v̂(s,w)=x(s)，得到简洁的SGD更新：wt+1=wt+α[Ut−v̂(St,wt)]x(St)。线性情况下只有一个最优解，因此保证收敛到全局最优。
Semi-gradient TD(0) with linear function approximation converges to the TD fixed point:
线性函数近似的半梯度TD(0)收敛到TD不动点：
wTD = A−1b, where A = E[xt(xt − γxt+1)T], b = E[Rt+1xt]
💡 收敛证明要点：矩阵A是正定的（yTAy>0），这保证了收敛性和A−1的存在性。关键在于平稳分布µ和策略π下的转移矩阵P使得D(I−γP)正定。
At the TD fixed point, the VE is bounded:
在TD不动点处，VE有界：
VE(wTD) ≤ 1⁄(1−γ) minw VE(w)
The asymptotic error of TD is no more than 1/(1−γ) times the smallest possible error (attained by MC). Because γ is often near 1, this factor can be large, but TD methods have vastly reduced variance and are often faster.
TD的渐近误差不超过MC可达到的最小误差的1/(1−γ)倍。由于γ通常接近1，该因子可能很大，但TD方法方差显著降低，通常更快。
⚠️ 关键警告：收敛的关键条件是状态按照on-policy分布更新。对于其他更新分布，带函数近似的自举方法实际上可能发散到无穷大（详见第11章）。
n-step Semi-gradient TD for Estimating v̂ ≈ vπ
────────────────────────────────────────────
Input: policy π, differentiable function v̂
Parameters: step size α > 0, positive integer n
Initialize weights w arbitrarily
Loop for each episode:
Initialize and store S₀ ≠ terminal; T ← ∞
Loop for t = 0, 1, 2, ...:
If t < T: take action per π, observe Rt+1, St+1
τ ← t − n + 1
If τ ≥ 0:
G ← Σ γi−τ−1 Ri (i = τ+1 to min(τ+n, T))
If τ+n < T: G ← G + γn v̂(Sτ+n, w)
w ← w + α [G − v̂(Sτ, w)] ∇v̂(Sτ, w)
Until τ = T − 1
9.5 特征构造 / Feature Construction for Linear Methods
Whether linear methods are efficient depends critically on how states are represented as features. Choosing features is an important way of adding prior domain knowledge to RL systems. A limitation of the linear form: it cannot capture interactions between features (e.g., feature i being good only in the absence of feature j).
线性方法是否高效关键取决于如何将状态表示为特征。选择特征是向RL系统添加先验领域知识的重要方式。线性形式的局限性：无法捕捉特征间的交互（如特征i仅在特征j不存在时才是好的）。
9.5.1 多项式 / Polynomials
For k-dimensional state space, each order-n polynomial feature is xi(s) = Πj=1k sjci,j where ci,j ∈ {0,1,...,n}. The order-n polynomial basis contains (n+1)k features — exponential growth limits practical use. Not recommended for online RL learning.
对于k维状态空间，每个n阶多项式特征为xi(s)=Πj=1ksjci,j，其中ci,j∈{0,1,...,n}。n阶多项式基包含(n+1)k个特征——指数增长限制了实际应用。不推荐用于在线RL学习。
9.5.2 傅里叶基 / Fourier Basis
The order-n Fourier cosine basis for s ∈ [0,1]k uses features xi(s) = cos(π sTci), where each cji ∈ {0,...,n}. It defines (n+1)k features. Fourier features can produce good performance vs polynomial and RBF bases. A useful trick: use different step sizes αi = α/‖ci‖ for each feature.
对于s∈[0,1]k的n阶傅里叶余弦基使用特征xi(s)=cos(πsTci)，其中每个cji∈{0,...,n}。它定义(n+1)k个特征。傅里叶特征相比多项式和RBF基可产生良好性能。实用技巧：对每个特征使用不同步长αi=α/‖ci‖。
9.5.3 粗编码 / Coarse Coding
Coarse coding represents states with overlapping binary features (e.g., circles in state space). If state is inside a circle, the feature is 1 (present), otherwise 0 (absent). Generalization is controlled by the size, density, and shape of receptive fields. Wider features → broader initial generalization, but final accuracy is controlled more by the total number of features.
粗编码用重叠的二值特征（如状态空间中的圆）表示状态。如果状态在圆内，特征为1（存在），否则为0（不存在）。泛化由感受野的大小、密度和形状控制。更宽的特征→更广泛的初始泛化，但最终精度更多由特征总数控制。
9.5.4 瓦片编码 / Tile Coding
Tile coding is a form of coarse coding for multi-dimensional continuous spaces that is flexible and computationally efficient. Key ideas:
- Tiling: a partition of state space (e.g., a grid)
- Multiple overlapping tilings offset by fractions of a tile width
- Each state activates exactly one tile per tiling (n features total for n tilings)
- Use α = 1/n for one-trial learning, or α = 1/(10n) for gradual learning
- Asymmetric offsets (e.g., displacement (1,3)) preferred over uniform offsets to avoid diagonal artifacts
- Hashing reduces memory by randomly collapsing large tilings into smaller tile sets
瓦片编码是多维连续空间的粗编码形式，灵活且计算高效。核心思想：
- 瓦片集（Tiling）：状态空间的一个划分（如网格）
- 多个重叠瓦片集，以瓦片宽度的分数偏移
- 每个状态在每个瓦片集中恰好激活一个瓦片（n个瓦片集共n个特征）
- 用α=1/n实现一次学习，或α=1/(10n)实现渐进学习
- 非对称偏移（如位移(1,3)）优于均匀偏移，避免对角线伪影
- 哈希通过随机将大瓦片集折叠为小瓦片集来减少内存
9.5.5 径向基函数 / Radial Basis Functions
RBF features have Gaussian response: xi(s) = exp(−‖s − ci‖2 / 2σi2). They produce smooth, differentiable approximate functions. Primary advantage over binary features is smoothness. In high dimensions, tile coding edges are more important and RBFs become harder to control. RBF networks that also adjust centers/widths are nonlinear approximators with greater complexity.
RBF特征具有高斯响应：xi(s)=exp(−‖s−ci‖2/2σi2)。它们产生平滑、可微的近似函数。相比二值特征的主要优势是平滑性。在高维空间中，瓦片编码的边缘更重要，RBF变得更难控制。同时调整中心/宽度的RBF网络是非线性近似器，复杂度更高。
9.6 步长参数的手动选择 / Selecting Step-Size Parameters
A useful rule of thumb for linear SGD: if you want to learn in about τ experiences with substantially the same feature vector:
线性SGD步长选择的实用经验法则：如果你希望在大约τ次大致相同特征向量的经验后学习：
α ≈ ( τ · E[xTx] )−1
In the tabular case, α = 1/τ means the estimate approaches the mean target after about τ experiences. For tile coding with n tilings and binary features, xTx = n (constant), so α = 1/(τn).
在表格情况下，α=1/τ意味着估计在约τ次经验后接近平均目标。对于n个瓦片集和二进制特征的瓦片编码，xTx=n（常数），所以α=1/(τn)。
9.7 非线性函数近似：人工神经网络 / ANNs
Artificial Neural Networks (ANNs) are widely used for nonlinear function approximation. A feedforward ANN has input layer, hidden layers, and output layer. Each unit computes a weighted sum then applies an activation function (sigmoid, ReLU, etc.).
人工神经网络（ANN）广泛用于非线性函数近似。前馈ANN有输入层、隐藏层和输出层。每个单元计算加权和然后应用激活函数（sigmoid、ReLU等）。
Universal Approximation Theorem (Cybenko, 1989): An ANN with a single hidden layer containing enough sigmoid units can approximate any continuous function on a compact region to any accuracy. However, deep architectures (many hidden layers) are often needed for complex AI tasks — they create hierarchical abstractions.
万能近似定理（Cybenko, 1989）：包含足够多sigmoid单元的单隐藏层ANN可以任意精度逼近紧区域上的任何连续函数。然而，复杂AI任务通常需要深度架构（多个隐藏层）——它们创建层次化抽象。
Key training techniques for deep ANNs:
- Backpropagation: alternating forward/backward passes to compute gradients
- Dropout: randomly removing units during training to prevent overfitting
- Batch normalization: normalizing between-layer signals using mini-batch statistics
- Deep residual learning: skip connections that learn residual functions
- Deep convolutional networks: specialized for spatial arrays (images), with shared-weight feature maps and subsampling layers
深度ANN的关键训练技术：
- 反向传播：交替前向/后向传播来计算梯度
- Dropout：训练期间随机移除单元以防止过拟合
- 批归一化：使用小批量统计量归一化层间信号
- 深度残差学习：跳跃连接学习残差函数
- 深度卷积网络：专用于空间阵列（图像），具有共享权重特征图和子采样层
9.8 最小二乘TD / Least-Squares TD (LSTD)
LSTD is the most data-efficient form of linear TD(0). Instead of iterating, it directly estimates A and b, then computes wTD = Â−1b̂:
LSTD是线性TD(0)最高数据效率的形式。它不迭代，而是直接估计A和b，然后计算wTD=Â−1b̂：
Ât = Σk=0t−1 xk(xk − γxk+1)T + εI, b̂t = Σk=0t−1 Rk+1xk
Using the Sherman-Morrison formula, the inverse can be maintained incrementally with O(d2) per-step computation. LSTD requires no step-size parameter (but needs ε > 0). Drawback: it never forgets, problematic when target policy changes in control.
使用Sherman-Morrison公式，可以以每步O(d2)的计算增量维护逆矩阵。LSTD不需要步长参数（但需要ε>0）。缺点：永不遗忘，在控制中目标策略变化时有问题。
Complexity comparison: Semi-gradient TD(0) = O(d) per step, LSTD = O(d2) per step. Whether LSTD's greater data efficiency is worth the computational cost depends on d, the importance of fast learning, and other system costs.
复杂度比较：半梯度TD(0)=每步O(d)，LSTD=每步O(d2)。LSTD更高的数据效率是否值得计算成本取决于d、快速学习的重要性以及其他系统成本。
9.10 基于核的函数近似 / Kernel-based Approximation
A kernel function k(s, s') measures the strength of generalization from s' to s. Kernel regression computes a kernel-weighted average of all stored targets:
核函数k(s,s')衡量从s'到s的泛化强度。核回归计算所有存储目标的核加权平均：
v̂(s, D) = Σs'∈D k(s, s') g(s')
Any linear parametric method with features x(s) can be recast as kernel regression with k(s,s') = x(s)Tx(s'). The kernel trick: for many feature sets, k(s,s') has a compact form computable without working in the d-dimensional feature space — enabling efficient computation in high-dimensional feature spaces.
任何带特征x(s)的线性参数方法都可以转化为核回归，其中k(s,s')=x(s)Tx(s')。核技巧：对于许多特征集，k(s,s')有紧凑形式，无需在d维特征空间中计算——从而在高维特征空间中实现高效计算。
9.11 Interest与Emphasis / Looking Deeper at On-policy Learning
So far all encountered states were treated equally. We now introduce interest It ≥ 0 — how much we care about accurately valuing the state at time t — and emphasis Mt ≥ 0 which multiplies the update:
到目前为止，所有遇到的状态被平等对待。现在引入interest It≥0——我们对准确评估t时刻状态的关注程度——以及乘以更新量的emphasis Mt≥0：
wt+n = wt+n−1 + α Mt [Gt:t+n − v̂(St, wt+n−1)] ∇v̂(St, wt+n−1)
Mt = It + γn Mt−n, with Mt = 0 for all t < 0
Example 9.4: In a 4-state MRP (values 4,3,2,1), with 2 parameters (w1, w2), if we only care about the first state (I=1, others I=0), the interest/emphasis methods learn w1=4 (exactly correct!), while standard methods converge to w1=3.5.
例9.4：在4状态MRP（值4,3,2,1）中，用2个参数(w1,w2)，如果我们只关心第一个状态（I=1，其他I=0），interest/emphasis方法学到w1=4（完全正确！），而标准方法收敛到w1=3.5。