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)}w​B(i)​​ 是第 iii 次实验被选中臂的期望收益，w∗w^*w​∗​​ 是最佳选择臂的收益。

基于规则

仅探索

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

仅利用

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

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

ϵ\epsilonϵ - 贪心法

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

Softmax

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

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

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

有模型学习

Markov Decision Process

Q-learning

可用于推荐系统 [0.1]

免模型学习

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

蒙特卡洛强化学习

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

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

\pi^\epsilon = \begin{cases} \pi(x), &以概率 1 - \epsilon \\ A 中以均匀概率选取的动作，&以概率 \epsilon \end{cases}

时序差分学习

模仿学习

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

直接模仿学习

首先获取人类专家的决策轨迹数据 \{\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 τ​i​​=⟨s​1​i​​,a​1​i​​,s​2​i​​,s​2​i​​,...,s​n​i​​+1​i​​⟩

其中 nin_in​i​​ 为第 iii 条轨迹中的转移次数

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

D={(s1,a1),(s2,a2),...,(s∑i=1mni,a∑i=1mni)}D=\{(s_1, a_1), (s_2, a_2), ..., (s_{\sum^m_{i=1} n_i}, a_{\sum_{i=1}^m n_i})\} D={(s​1​​,a​1​​),(s​2​​,a​2​​),...,(s​∑​i=1​m​​n​i​​​​,a​∑​i=1​m​​n​i​​​​)}

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

逆强化学习

Reference

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

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