今天主要围绕 tile coding 的 course project 做了一些整理。相比前两天更偏实现的内容，今天更多是在想一个问题：
固定的稀疏表示会如何影响 online reinforcement learning 中的 value learning、policy learning 和 credit assignment？
Tile coding 是一个很适合观察这个问题的工具。它不像 neural network 那样把 representation 学习过程藏在参数里，而是把 inductive bias 直接暴露出来：tile 的分辨率、tiling 的数量、offset 的设计，都会决定哪些状态共享参数，也会影响 value estimate 和 policy update 如何泛化。
这个方向也和 Alberta Plan 中几个主题有关：
- Streaming learning: 所有算法都从一条 interaction stream 中在线更新，不使用 replay buffer。
- Agent state and representation: tile coding 显式定义了 value function 和 policy 使用的 feature。
- Eligibility traces: trace decay 控制 TD error 在时间上的 credit assignment 范围。
1. Basic Idea#
Tile coding 将连续状态映射为稀疏二进制特征：
$$ \phi(s) \in \{0,1\}^d . $$每个时间步只有少量 feature 被激活。在线性函数近似下，state-value 和 action-value 可以写成：
$$ \hat{v}(s; w) = w^\top \phi(s), $$$$ \hat{q}(s,a; w) = w^\top \phi(s,a). $$这里 $\phi$ 的结构决定了 value generalization 的方式。coarse tiling 会增加参数共享，但可能 alias 掉不同状态；fine tiling 可以减少 aliasing，但更新更局部，也可能更不 sample efficient。
对于 TD learning，基本的 prediction error 是：
$$ \delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}; w_t) - \hat{v}(S_t; w_t). $$如果加入 eligibility trace，可以维护一个过去 feature 的衰减记忆：
$$ e_t = \gamma \lambda e_{t-1} + \phi(S_t), $$并用下面的方式更新参数：
$$ w_{t+1} = w_t + \alpha \delta_t e_t . $$因此，tile coding 和 trace 可以看成两类 credit assignment：前者控制 value update 在状态空间中传播到哪里，后者控制 TD error 在时间上向过去传播多远。
对于 policy learning，同样的 tile-coded feature 也可以用于参数化随机策略：
$$ \pi_\theta(a|s) = \pi(a \mid \theta^\top \phi(s)). $$Monte Carlo policy-gradient update 可以写成：
$$ \theta_{t+1} = \theta_t + \alpha G_t \nabla_\theta \log \pi_\theta(A_t|S_t). $$Actor-Critic 则用 bootstrapped TD error 代替完整 return $G_t$，把 $\delta_t$ 作为低方差的 advantage estimate。这样同一套 representation 可以同时在 value targets、policy-gradient targets 和 value-assisted policy updates 下被比较。
2. Experimental Setting#
目前实验主要使用两个连续状态控制任务：
- Acrobot-v1: 用来测试 tile-coded action-value learning 和 SARSA($\lambda$) 的 temporal credit assignment。
- Pendulum-v1: 用来测试 tile-coded policy gradient 和 actor-critic 是否能支持 continuous-action policy learning。
当前主要比较几类方法：
- Q-learning for value learning
- SARSA($\lambda$) for trace-based credit assignment
- REINFORCE for stochastic policy learning
- Actor-Critic for value-assisted policy update
3. Preliminary Results#
当前初步结果如下：
| Task | Method | Training episodes | Final 100-episode average return | Best 100-episode average return | 5-episode evaluation return |
|---|---|---|---|---|---|
| Acrobot-v1 | Q-learning | 15,000 | -137.88 | -129.53 | -124.00 |
| Acrobot-v1 | SARSA($\lambda$) | 15,000 | -105.95 | -92.43 | -88.60 |
| Pendulum-v1 | REINFORCE | 10,000 | -171.19 | -135.74 | -179.02 |
| Pendulum-v1 | Actor-Critic | 10,000 | -181.40 | -133.41 | -180.60 |
初步结果上，Acrobot-v1 中 SARSA($\lambda$) 明显优于 one-step Q-learning。这个现象比较符合直觉：在 sparse tile-coded features 下，eligibility traces 可以把 TD error 更有效地分配给过去访问过的 state-action features。
Pendulum-v1 的结果则更微妙。REINFORCE 和 Actor-Critic 都能从初始低回报区域中提升出来，但最终 evaluation return 仍然比较接近。这说明 tile coding 可以支持 continuous-action policy learning，不过 policy update 对 variance 和稳定性还是比较敏感。
4. Trace Sensitivity#
另外还对 SARSA($\lambda$) 做了一个 trace sensitivity study。比较明显的是，不同 $\lambda$ 对 sample efficiency 的影响比对 wall-clock time 的影响更大。
| $\lambda$ | Final 100-episode average return | Best 100-episode average return | Mean time per 100 episodes | Total logged training time |
|---|---|---|---|---|
| 0.9 | -105.95 | -92.43 | 1.65 s | 247.62 s |
| 0.7 | -101.37 | -97.74 | 1.58 s | 236.59 s |
| 0.3 | -118.19 | -111.32 | 1.62 s | 242.97 s |
较大的 trace value，比如 $\lambda=0.9$，在 early 和 middle training stage 学得更快，并取得了更好的 peak moving-average return。较小的 $\lambda$ 学得更慢，说明它把 credit assignment 限制得更局部。
这也让我感觉，tile coding 的空间泛化和 eligibility traces 的时间泛化其实是在解决类似的问题：如何让一次更新影响到“应该被影响”的状态或时间步。
5. Takeaway#
目前的 takeaway 是：
- Tile coding 的设计并不只是工程细节，它直接决定了 value function 的泛化方式。
- 在 Acrobot 这类任务里，eligibility traces 对 sparse representation 很有帮助。
- 在 continuous-action policy learning 中，tile coding 可以工作，但 policy gradient 的 variance 和 update stability 仍然是主要问题。
- 后续还需要更系统地比较 tiling 数量、tile resolution、step size 和 $\lambda$ 的影响。
整体上，这个项目更像是用一个 classical representation method，去观察 online RL 中 representation、value learning、policy learning 和 credit assignment 之间的关系。