学习笔记: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016
一般的老O虎O机只有一个臂(杆)。你塞10个硬币,拉一下杆,老O虎O机可能会吐出来一两个硬币,或者100个硬币。 多臂老O虎O机有多个杆(象征着多个行动(action),每个杆有自己特有的吐钱逻辑)。 注意:每个杆的吐钱概率可能是固定的(stationary),也可能是不固定的(non-stationary)。不固定在现实中更常见。 多臂老O虎O机问题就是在许多次尝试后,找到一个有效收益的策略。 多臂老O虎O机问题是统计学、工程、心理学的一个经典问题。不要小看了这个问题,很多权威都研究过。 在强化学习方面,我们通过这个问题,可以了解强化学习的基本概念和算法的思路。其中包括:
在讨论算法前,我们先考虑判断算法好坏的标准。
在决定第t次的行动\(A_t\)时,使用下面的算法。 A_t = \underset{a}{argmax} Q_t(a) \\ where \\ 1_{A_i=a} = \begin{cases} 1, if A_i = a \\ 0, otherwise \end{cases}
如何计算\(Q_t\)。 算法 \begin{array} \\ Q_t & = \frac{1}{t-1} \sum_{i=1}^{t-1} R_i \text{ : this method need memory all } R_i. \\ & = Q_{t-1} + \frac{1}{t-1} \left [ R_{t-1} - Q_{t-1} \right ] \text{this method is better, just need memory last } R_{t-1}, Q_{t-1}. \end{array}
一个替代算法。用步长\(\alpha\) 代替$ \frac{1}{t-1}$。 算法 Q_t = Q_{t-1} + \alpha \left [ R_{t-1} - Q_{t-1} \right ]
解释 这个算法利于解决非稳定(non-stationary)问题。 非稳定(non-stationary)问题意味着\(q_*(a)\)是会发生变化的。因此,最近几次的奖赏更具代表性。 \(\alpha\)越大,意味着最近奖赏的权重越大。 这里也可以看到梯度计算的影子。
优化初始值\(Q_1(a)\),如果赋值越大,会鼓励探索。 初始值为0时,ε - 贪婪方法(ε=0.1) 好于 ε - 贪婪方法(ε=0.01) 好于 贪婪方法。 看来冒一定风险还是有好处的。 初始值为5的贪婪方法 好于 ε - 贪婪方法(ε=0.1)。 有钱人更容易成功。
可理解为求每个行动的最大可信值,选择最大可信值最大的行动。
算法 A_t = \underset{a}{argmax} \left [ Q_t(a) + c \sqrt{\frac{\log{t}}{N_t(a)}} \right ] \\ where \\ c \text{ : > 0, controls the degree of exploration. bigger c means more exploration.} \\ \text{if } N_t(a) = 0 \text{, then a is considered to be a maximizing action.}
算法理解 这个算法在计算:第t次的行动应该是什么?
我们没有说:“第t次的最优行动应该是什么?”。为什么不说最优呢? 因为,强化学习的目的是总体最优,不是局部最优,因此“第t次的最优行动”不是强化学习最求的目标。
c是一个可调的参数。我们在理解中不用太关心它,当它是\(1\)好了。
H_1(a) = 0, \forall a \\ \text{After action } A_t \text{ and receiving the reward } R_t, \\ H_{t+1}(A_t) = H_t(A_t) + \alpha(R_t - \bar{R}_t)(1- \pi_t(A_t)) \text{, and} \\ H_{t+1}(a) = H_t(a) - \alpha(R_t - \bar{R}_t)\pi_t(a) , \forall a \ne A_t \\ \bar{R}_t = \frac{\sum R_t}{t} \\ where \\ \alpha \text{ - step size parameter.} \\ \bar{R}_t \text{ - the average of all the rewards up through and including time t.}