Example 8.2 Mountain–Car Task

前面讲过coarse coding，Tile Coding是Coarse Coding的一种，特别适合用于多维连续空间。之前降到Coarse Coding，多个特征，特征与特征之间存在互相覆盖。而在Tile Coding中，特征的receptive field（感受野）作为输入空间的一个分区。每个分区称为tiling，分区里面的元素称为tile。如下图所示，是一个二维状态空间的最简单的分区，有4个分区。每个分区通过一定的位移形成新的分区。这四个分区对应4个特征。状态空间中的每个点在每个tiling中都能找到对应的tile，有且只有一个tile，每个点的特征数都是一样的——4个。

假设有m个tiling，则某状态由m个tile组成。状态之间的tile可能是相同的。当某一状态更新，则另一状态也可能发生变化。

接下来举个例子。
sutton的rl第一版本的8.2案例，第二版本的10.1。
如图，有一辆小车，通过向左，

小车的发动机能给一个向前或向后的动力，小车的发动机有三个选择：向前（+1）、向后（-1）和不发动（0）。小车根据简单化的物理规则行动，它的位置$x_t$和速度$\dot{x}_t$根据以下更新：

$x_{t+1} \dot{=} bound [x_t+\dot{x}_{t+1}]$
$\dot{x}_{t+1} \dot{=} bound [\dot{x}_t+0.001A_t-0.0025cos(3x_t)]$
其中bound规定 $-1.2 \le x_{t+1} \le 0.5$以及 $-0.07 \le \dot{x}_{t+1} \le 0.07$。
另外，如果 $x_{t+1}$到达最左边，那么 $\dot{x}_{t+1}$，也就是加速度被设为0。到达最右边，则episode结束。每个episode从一个随机的位置 $x_t \in [-0.6,-0.4)$开始，开始时速度为0。为了将连续的状态变量用二元特征表示，我们使用grid-tiling（tile coding的一种）。

我们使用的tile-coding是网上公开的python3代码。使用下面两行代码就行了：

iht = IHT(2048)
features = tiles(iht, 8, [8*x/(0.5+1.2), 8*xdot/(0.07+0.07)], A) 

IHT是处理特征的结构，tiles (ihtORsize, numtilings, floats, ints=[], readonly=False)根据floats和ints返回特征tile。返回的特征tile维数为numtilings。floats为当前状态，ints为采取的行动。

根据rl第二版本的伪代码（Episodic Semi-gradient Sarsa for Control）跑了一下：

其实和Sarsa差不多，除了$\nabla \hat{q}(S,A,\theta)$体现了梯度。向量微分算子，Nabla算子（nabla operator），又称劈形算子，倒三角算子，是一个微分算子，符号为$\nabla$。定义为$\nabla=\frac{d}{dr}$

根据rl第一版本的伪代码：

这里多了eligibility trace。对比两个实验，发现并无多大差别，所以我还是搞不清eligibility trace的作用。。

实验代码：https://github.com/Mandalalala/Reinforcement-Learning-an-introduction/blob/master/Chapter%208/Example_8_2_Mountain_Car_Task.ipynb