1. Intro of Tile Coding#
今天大致了解了强化学习中的 Tile Coding 技术。传统的表格型价值学习方法需要为每个离散状态或状态—动作对分别维护一个价值，但对于连续状态空间，这种方法无法直接应用，因为连续状态的数量理论上是无限的。Tile Coding 通过多组相互错位的网格划分（tilings）覆盖连续状态空间，并利用不同的 offset 使各组网格的边界彼此错开。对于给定状态或状态—动作对，每个 tiling 中都会有一个对应的 tile 被激活，其价值可以由所有激活 tile 对应权重的加权和近似表示。在学习过程中，强化学习算法根据 TD error 更新这些激活 tile 的权重，从而逐步学习价值函数，并进一步通过价值函数选择动作、得到策略。
2. Process of Tile Coding#
对于连续状态$s$和动作$a$，Tile Coding 将其编码为稀疏二进制特征：$\phi(s,a)\in\{0, 1\}^d$。假如使用$M$个tilings，则每个状态-动作对通常会激活M个tiles。定义激活tile的索引集合为：$\mathcal{A}(s,a)=\{i_1, i_2, \dots, i_M\}$。因此动作价值函数可以表示为$\hat{Q}(s,a; w)= \sum_{i\in\mathcal{A}(s,a)} w_i$
强化学习算法计算TD-error更新激活tile对应的参数权重。如Q-learning算法：
$$ \delta_t=R_{t+1}+\gamma\hat{Q}(S_{t+1},a^{\prime};w)-\hat{Q}(S_t, A_t; w) $$由于只有激活tile对应的特征值为1，因此只需要更新$i\in\mathcal{A}(S_t, A_t)$对应的权重：
$$ w_i\leftarrow w_i + \frac{\alpha}{M}\delta_t $$参数更新后 ，利用学习得到的动作价值函数：$\hat{Q}(s,a; w)$选择动作。常用方法是$\epsilon$-greedy策略：
$$ A_t= \begin{cases} \text{random-choice}(\mathcal{A}), & \text{以概率 } \epsilon,\\[6pt] \displaystyle \arg\max_{a\in\mathcal A}\hat Q(S_t,a;\mathbf w), & \text{以概率 } 1-\epsilon. \end{cases} $$