第16章 强化学习

16.1 任务与奖励

强化学习任务对应了四元组E=< X,A,P,R >

X:为一个状态

A:指一个动作

P:为从状态X_i转移到状态X_j的概率。

R:指从状态X_i到X_j的奖励

在强化学习的任务中目的就是为了找到能使长期累积的奖赏到达最大值的一个策略。

马尔可夫性质（英语：Markov property）是概率论中的一个概念，因为俄国数学家安德雷·马尔可夫得名。

当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态；

换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的，那么此随机过程即具有马尔可夫性质。

具有马尔可夫性质的过程通常称之为马尔可夫过程。 [1]

一句换就是：下一个出现什么样的状态只依赖于当前状态，与历史信息无关。

16.2 K-摇臂赌博机

16.2.1 探索与利用

为了最大化奖赏，一个简单的想法就是最大化每一步的奖赏。即单步强化学习。

单步强化学习分为两个类型动作，一个是探索类型的动作，一个是利用类型的动作。

探索即平均执行每一个动作，统计每个动作带来的奖赏。

利用即通过现有的数据，找到当前状态历史上那个动作能得到最大奖赏，就采取哪个动作。

可知要先进行一定次数的探索，然后得到较好的统计信息后，再利用这些信息，以期达到最大奖赏。

16.2.2 $\epsilon$-贪心算法

根据探索次数和利用次数的比例，有了$\epsilon$-贪心算法。

即以$\epsilon$的概率进行探索，以1-$\epsilon$的概率进行利用。

小优化：

可知前期需要较多的探索，后期则偏向与利用，那么$\epsilon$应该随着训练的进行而不断减小。

所以可以令$\epsilon=\frac{1}{\sqrt t}$

16.2.3 softmax算法

softmax算法不将探索和利用划分开了。

每次按照获得奖励大小的概率来选取动作，并根据结果，更新动作A_i获得的平均奖励大小。

其选取某个动作的概率公式是基于Boltzmann分布的：

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

设一个K-摇臂赌博机有两个摇把，即2-摇臂赌博机。

摇臂1，以0.4返回1，以0.6返回0

摇臂2，以0.2返回1，以0.8返回1

现在采用上述两种方法测试。

Bandit_Model.py:

import random

class Bandit_2_arms:

    def __init__(self):
        # 有两个摇臂，摇臂1，以0.4概率返回1，摇臂2以0.2概率返回1
        self.p = [0.4, 0.2]
        self.my_random = random.Random()
        self.my_random.seed(1591532)

    def wave(self, arm_no):
        t = self.my_random.random()
        reward = 0
        if t < self.p[arm_no]:
            reward = 1
        else:
            reward = 0
        return reward

if __name__ == '__main__':
    bandit = Bandit_2_arms()
    for i in range(10):
        reward = bandit.wave(1)
        print(reward)

epsilon_algorithm:

import random

class epsilon:

    def __init__(self, e=0.1):
        # 一开始摇臂1，2的平均奖励都为0
        self.Q = [0, 0]
        # 记录每个摇臂被摇的次数
        self.cnt = [0, 0]
        # 探索的概率为e
        self.e = e
        self.test_use_random = random.Random()
        self.test_use_random.seed(789456)
        self.which_arm_random = random.Random()
        self.which_arm_random.seed(456123)
        self.total_reward = 0

    def action(self):
        arm_no = 0
        t = self.test_use_random.random()
        if t < self.e:
            # 如果是探索，那么随机选取一个摇臂
            arm_no = self.which_arm_random.randint(0, 1)
        else:
            arm_no = self.Q.index(max(self.Q))
        return arm_no

    def update(self, arm_no, reward):
        self.total_reward += reward
        self.Q[arm_no] = self.Q[arm_no] * self.cnt[arm_no] + reward
        self.cnt[arm_no] += 1
        self.Q[arm_no] /= self.cnt[arm_no]

    def get_average_reward(self):
        sum_cnt = 0
        for i in range(len(self.cnt)):
            sum_cnt += self.cnt[i]
        if sum_cnt < 1:
            sum_cnt = 1
        return self.total_reward/sum_cnt

softmax_algorithm:

import math
import random

class softmax:

    def __init__(self, temperature=0.1):
        self.Q = [0, 0]
        self.cnt = [0, 0]
        self.total_reward = 0
        self.temperature = temperature
        self.which_arm_random = random.Random()
        self.which_arm_random.seed(789456)

    def P(self, arm_no):
        p = math.pow(math.e, self.Q[arm_no]/self.temperature)
        sum_p = 0
        for i in range(2):
            sum_p = sum_p + math.pow(math.e, self.Q[i]/self.temperature)
        p_arm = p/sum_p
        return p_arm

    def action(self):
        arm_no = 0
        t = self.which_arm_random.random()
        if t < self.P(0):
            arm_no = 0
        else:
            arm_no = 1
        return arm_no

    def update(self, arm_no, reward):
        self.total_reward += reward
        self.Q[arm_no] = self.Q[arm_no] * self.cnt[arm_no] + reward
        self.cnt[arm_no] += 1
        self.Q[arm_no] /= self.cnt[arm_no]

    def get_average_reward(self):
        sum_cnt = 0
        for i in range(len(self.cnt)):
            sum_cnt += self.cnt[i]
        if sum_cnt < 1:
            sum_cnt = 1
        return self.total_reward/sum_cnt

main.py:

from Bandit_Model import Bandit_2_arms
from epsilon_algorithm import epsilon
from softmax_algorithm import softmax
import matplotlib.pylab as pl

def drew_lines(x, y):
    pl.plot(x, y)
    pl.grid(True)
    pl.scatter(x, y)


if __name__ == '__main__':
    bandit = Bandit_2_arms()
    epsilon_a = epsilon(0.1)
    softmax_a = softmax(0.1)

    n = 100

    epsilon_average_reward = []
    softmax_average_reward = []

    for i in range(n):
        arm_no = epsilon_a.action()
        reward = bandit.wave(arm_no)
        epsilon_a.update(arm_no, reward)
        epsilon_average_reward.append(epsilon_a.get_average_reward())

    bandit = Bandit_2_arms()

    for i in range(n):
        arm_no = softmax_a.action()
        reward = bandit.wave(arm_no)
        softmax_a.update(arm_no, reward)
        softmax_average_reward.append(softmax_a.get_average_reward())

    x = range(0, n)
    drew_lines(x, epsilon_average_reward)
    drew_lines(x, softmax_average_reward)
    pl.show()

还是很依赖于摇臂机的初始种子的，不过到最后曲线都是趋近于0.4，与书上的曲线不一致。。。 经我测试epsilon算法好的次数多一点。

16.3 有模型学习

假设四元组的值已经知道了。

即E=< X,A,P,R >中的状态X已知， A动作已知， 从X_i进行动作A_k转移X_j的概率已知，从X_i转移到X_j获得奖励R已知。

16.3.1 策略评估

再四元组已知的情况下，可以计算一个策略获得奖励的期望。

设$V^{\pi}(x)$表示从状态x出发，使用策略$\pi$累计获得的奖赏。

设$Q^{\pi}(x, a)$表示从状态x执行a动作后，再使用策略$\pi$所获得的累计奖赏。

由于所有的概率都知道所以可以算全部的情况。随意可以算出策略$\pi$的期望。

16.3.2 策略改进

$$ {\pi}^*=argmax\sum_{x\inX}V^{\pi}(x) $$

由于所有的概率都知道，所以求解，最优解可以使用动态规划的思想，写出状态转移方程，打表找出最优解。

16.3.3 策略迭代与值迭代

不断优化策略直至策略不变，叫做策略迭代。类似的叫值迭代。

16.4 免模型学习

为了应对状态转移概率不可知，奖赏不可知的问题，提出了免模型学习。

即利用统计信息来近似找到一个，概率转移的表，和奖励表。

16.4.1 蒙特卡罗强化学习

将< x_0, a_0, r_1, ..., x_k, a_k, r_k, ...>叫做一个\pi策略的轨迹。

一个轨迹就有了一些探测数据，根据这个数据修正Q，根据修正后的Q，继续使用策略\pi产生一条新的轨迹，不断迭代，得到更优的解。

即探测轨迹+\epsilon算法，用统计数据来代替原来知道的奖励和概率。