Reinforce Learning

强化学习笔记。

K-摇臂赌博机

赌徒投币后选择一个摇臂,每个摇臂以一定概率吐出硬币。

算法需要最小化累计遗憾

\begin{align} R_T &= \sum_{i=1}^{T} \bigg(w_{opt} - w_{B(i)} \bigg) \\ &=Tw^* - \sum_{i=1}^{T} w_{B(i)} \end{align}

其中 wB(i)w_{B(i)} 是第 ii 次实验被选中臂的期望收益,ww^* 是最佳选择臂的收益。

基于规则

仅探索

将所有机会平均分给么个摇臂

仅利用

按下目前最优的摇臂,如果多个同为最优,随机选择一个最优。

以上两种方法,是强化学习面临的『探索 - 利用窘境』(Exploration-Exploitation dilemma),折衷二者,以获得更优方案。

ϵ\epsilon - 贪心法

ϵ\epsilon 的概率进行探索;以 1ϵ1-\epsilon 的概率进行利用。

Softmax

若某些摇臂的平均奖赏高于其他摇臂,则被选取的概率 PP 更高

P(k)=eQ(k)τi=1KeQ(i)τP(k)=\frac{e^{\frac{Q(k)}{\tau}}}{\sum_{i=1}^{K}e^{\frac{Q(i)}{\tau}}}

其中 Q(k)Q(k) 记录当前摇臂的平均奖赏;τ>0\tau > 0 称为温度,趋于 0 时仅利用,区域无穷大时仅探索。

有模型学习

假设任务对应的马尔科夫决策过程四元组 E=<X,A,P,R>E=<X,A,P,R> 已知,即模型已知,此时学习问题称为有模型学习。

Markov Decision Process

马尔可夫决策过程四元组 E=<X,A,P,R>E=<X,A,P,R> 中,四个变量已知。

那么可以对任意策略 π\pi 做评估,求累计奖赏和折扣累计奖赏:

V_T^\pi(x) = \mathbb E_\pi [\frac{1}{T} \sum_{t=1}^{T} r_t | x_0 = x] \\ V_\gamma^\pi(x) = \mathbb E_\pi [\frac{1}{T} \sum_{t=1}^{T} \gamma^t r_t | x_0 = x] \\

因此,也可以对策略 π\pi 进行改进、评估。

免模型学习

现实世界中,环境的转移概率、奖赏函数往往难以得知,甚至很难知道环境中一共有多少状态。若学习不依赖于环境建模,则称为免模型学习。

蒙特卡洛强化学习

蒙特卡洛方法又称模拟统计方法,通过随机数来解决计算问题,如通过洒豆子估算圆形的面积。

蒙特卡洛强化学习,通过多次采样,然后求平均累计奖赏来作为期望累积奖赏的近似。然后借鉴 \epsilon - 贪心法,在下一步执行策略。

同策略蒙特卡洛强化学习:

异策略蒙特卡洛强化学习:(在策略评估时引入贪心策略,在策略改进时改进原始策略)

时序差分学习

Sarsa

Q-learning

训练方法

Q(S,A)(1α)Q(S,A)+α[R+γmaxαQ(S,a)]Q(S,A) \leftarrow (1-\alpha) \cdot Q(S,A) + \alpha \cdot [R+\gamma \cdot \max_\alpha Q(S',a)]

其中 Q 是动作效用函数,根据当前状态 SS 和行动 AA 给出评分,指导下一步行动;γ\gamma 是折扣系数;α\alpha 是学习率;RR 是奖赏;这里用 ϵgreedy\epsilon-greedy 方法进行探索和利用。

可用于推荐系统 [0.1]

Flappy Bird 例子 知乎

Stanford Lecture Youtube

模仿学习

通过借助专家决策过程的范例,加速学习过程。

直接模仿学习

首先获取人类专家的决策轨迹数据 \{\tau_1, \tau_2, …, \tau_m\},每条轨迹包括状态和动作序列

τi=s1i,a1i,s2i,s2i,...,sni+1i\tau_i = \langle s_1^i, a_1^i, s_2^i, s_2^i, ..., s_{n_i+1}^i \rangle

其中 nin_i 为第 ii 条轨迹中的转移次数

我们可以把 ss 作为输出,aa 作为输出,通过有监督学习以下数据集,得到一个初始化的策略模型

D={(s1,a1),(s2,a2),...,(si=1mni,ai=1mni)}D=\{(s_1, a_1), (s_2, a_2), ..., (s_{\sum^m_{i=1} n_i}, a_{\sum_{i=1}^m n_i})\}

然后把学得的策略模型作为强化学习的输入

逆强化学习

Reference

[1] 《机器学习》周志华

[2] Bandit算法与推荐系统 http://geek.csdn.net/news/detail/195714

本文有帮助?