RL

Agent->Env: Action a
Env-->Agent: State x
Env-->Agent: Reward r

强化学习任务通常用马尔科夫决策过程(Markov Decision Process,简称 MDP)来描述：

机器处于环境$E$中，状态空间为$X$,其中每个状态$x \in X$是机器感知到的环境的描述，机器能采取的动作构成了动作空间$A$，若某个动作$a\in A$作用在当前状态$x$上，则潜在的转移函数$P$将使得环境从当前状态按某种概率转移到一另个状态，在转移到另一个状态的同时，环境会根据潜在的奖赏（reward）函数$R$反馈给机器一个奖赏。综合起来，强化学习任务对应了四元组$E=<X,A,P,R>$,其中$P:X\times A\times X \mapsto \mathbb{R}$指定了状态转移概率,$R:X \times A \times X \mapsto \mathbb{R}$指定了奖赏，在有的应用中，奖赏函数可能仅与状态转移有关，即$R: X \times X \mapsto \mathbb{R}$.

在环境中状态的转移，奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。
策略（policy）$\pi$的定义,根据这个策略，在状态$x$下就能得知要执行的动作$a=\pi(x)$，确定性动作表示为$\pi:X \mapsto A$,随机性动作表示为$\pi:X\times A \mapsto \mathbb{R}$，$\pi(x,a)$为状态$x$下选择动作$a$的概率，则有$\sum_a\pi(x,a)=1$

累计奖赏####

T步累积奖赏$E(\frac{1}{T}\sum_{t=1}^Tr_t)$
$\gamma$折扣累积奖赏$E(\sum_{t=0}^{{+\infty}\gamma}tr_{t+1})$

$K$-摇臂赌博机

$K$-要比赌博机有$K$个摇臂，赌徒在投入一个硬币后可选择按下其中一个要比，每个要比以一定的概率突出硬币，但这个概率赌徒并不知道，赌徒的目标是通过一定的策略最大化自己的奖赏，即获得醉倒的硬币
exploration-only：很好的估计每个要比的奖赏，失去选择最优摇臂的机会
exploitation-only：没有很好估计摇臂期望奖赏，很可能选不到最优的摇臂
因为尝试次数有限，加强了一方则会削弱另一方，面临“探索-利用窘境”(Exploration-Exploitation dilemma)

$\epsilon$-贪心####

每次尝试时，以$\epsilon$的概率进行探索，即以均匀概率随机选取一个摇臂，以$1-\epsilon$的概率进行利用，集选择当前平均奖赏最高的摇臂(若有多个，则随机选取一个)

class EpsilonGreedyPolicy(Policy):
    """
    The Epsilon-Greedy policy will choose a random action with probability
    epsilon and take the best apparent approach with probability 1-epsilon. If
    multiple actions are tied for best choice, then a random action from that
    subset is selected.
    """
    def __init__(self, epsilon):
        self.epsilon = epsilon

    def __str__(self):
        return '\u03B5-greedy (\u03B5={})'.format(self.epsilon)

    def choose(self, agent):
        if np.random.random() < self.epsilon:
            return np.random.choice(len(agent.value_estimates))
        else:
            action = np.argmax(agent.value_estimates)
            check = np.where(agent.value_estimates == action)[0]
            if len(check) == 0:
                return action
            else:
                return np.random.choice(check)

Softmax####

摇臂的概率的分配是基于Boltzmann分布
$$P(k)=\frac{e^{\frac{Q(k)}{\tau}}{\sum_{i=1}}{K}e^\frac{Q(i)}{\tau}}$$
其中，Q(i)记录当前摇臂的平均奖赏;$\tau>0$成为“温度”,$\tau$越小则平均奖赏高的摇臂被选取的概率越高。$\tau \rightarrow 0$则Softmax趋于“仅利用”，$\tau \rightarrow \infty$则Softmax趋于“仅探索”

class SoftmaxPolicy(Policy):
    """
    The Softmax policy converts the estimated arm rewards into probabilities
    then randomly samples from the resultant distribution. This policy is
    primarily employed by the Gradient Agent for learning relative preferences.
    """
    def __str__(self):
        return 'SM'

    def choose(self, agent):
        a = agent.value_estimates
        pi = np.exp(a) / np.sum(np.exp(a))
        """
        >>> a = np.array([[1,2,3], [4,5,6]])
        >>> np.cumsum(a)
        array([ 1,  3,  6, 10, 15, 21])
        """
        cdf = np.cumsum(pi)
        s = np.random.random()
        return np.where(s < cdf)[0][0]

def choose(self):
        action = self.policy.choose(self)
        self.last_action = action
        return action

def observe(self, reward):
    self.action_attempts[self.last_action] += 1

    if self.gamma is None:
        g = 1 / self.action_attempts[self.last_action]
    else:
        g = self.gamma
    q = self._value_estimates[self.last_action]

    self._value_estimates[self.last_action] += g*(reward - q)
    self.t += 1

对于离散状态空间,离散动作空间上的多不讲话学习人物，一种直接的办法是将每个状态上动作的选择看做一个$K$-摇臂赌博机问题，用强化学习任务的累计奖赏来代替$K$-摇臂赌博机算法中的奖赏函数，即可将赌博计算法用于每个状态

有模型学习###

$$E=<X,A,P,R>$$
机器已对模型进行了建模，能在机器内部模拟出与环境相同活近似的状况，对于任意状态$x,x'$和动作$a$,在$x$状态下执行动作$a$转移到$x'$状态的概率$P_{x \rightarrow x'}^a$是已知的，改转移所带来的奖赏$R_{x \rightarrow x'}^a$也是已知的
$V^\pi(x)$表示从$x$出发，使用策略$\pi$所带来的累积奖赏."状态值函数"(state value function)
$Q^\pi(x,a)$表示从$x$出发，执行动作$a$后再使用策略$\pi$带来的累积奖赏."状态-动作值函数"(state-action value function)
$$\left{\begin{array}{ll}V_T^{\pi(x)=E_\pi[\frac{1}{T}\sum_{t=1}}Tr_t|x_0=x], & \text{T步累积奖赏}\
V_\gamma^{\pi(x)=E_\pi[\sum_{t=0}}{+\infty}\gamma^tr_{t+1}|x_0=x], & \gamma\text{折扣累计奖赏}
\end{array}
\right.$$
$$\left{\begin{array}{ll}Q_T^{\pi(x,a)=E_\pi[\frac{1}{T}\sum_{t=1}}Tr_t|x_0=x,a_0=a], & \text{T步累积奖赏}\
Q_\gamma^{\pi(x,a)=E_\pi[\sum_{t=0}}{+\infty}\gamma^tr_{t+1}|x_0=x,a_0=a], & \gamma\text{折扣累计奖赏}
\end{array}
\right.$$
Bellman等式
$$
\begin{align}
V_T^{\pi(x)&=E_\pi[\frac{1}{T}\sum_{t=1}}Tr_t|x_0=x]\
&=E_\pi[\frac{1}{T}r_1+\frac{T-1}{T}\frac{1}{T-1}\sum_{t=2}^Tr_t|x_0=x]\
&=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}E_\pi[\frac{1}{T-1}\sum_{t=1}^{T-1}r_t|x_0=x'])\
&=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}V_{T-1}^\pi(x')) \tag{1.1} \
V_{\gamma}^\pi(x)&=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(R_{x \rightarrow x'}^a + \gamma V_{\gamma}^\pi(x')) \tag{1.2}
\end{align}
$$
P和R已知，才能进行全概率展开，类似于动态规划
停止准则，设置一个阈值$\theta$满足值函数的改变在一次迭代后改变小于$\theta$则停止$\max_{x\in X}|V(x)-V'(x)|<\theta$
通过状态值函数V，就能直接计算出状态-动作值函数
$$\left{\begin{array}{ll}Q_T^\pi(x,a)=\sum_{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}V_{T-1}^\pi(x'))\
Q_\gamma^\pi(x,a)=\sum_{x'\in X}P_{x \rightarrow x'}^a(R_{x \rightarrow x'}^a + \gamma V_{\gamma}^\pi(x'))\tag{1.3}
\end{array}
\right.$$

策略改进####

对某个策略的累计奖赏进行评估后，若发现它并非最有策略，则希望改进。理想的策略应能最大化累积奖赏
$$\pi^=\mathop{argmax}\pi\sum{x\in X}V^\pi(x)$$
一个强化学习任务可能有多个最优策略，最有策略所对应的值函数$V^$称为最优值函数，即
$$\forall x \in X:V^*(x)=V{\pi^}(x)$$
策略空间是所有状态上所有动作的组合，共有$|A|^{|X|}$种不同的策略
将动作的求和改为取最优，公式(1.1)(1.2)
$$\left{\begin{array}{ll}V_T^(x)=\mathop{max}{a \in A}\sum{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}V_{T-1}^(x'))\
V_\gamma^(x)=\mathop{max}{a \in A}\sum{x'\in X}P_{x \rightarrow x'}^a(R_{x \rightarrow x'}^a + \gamma V_{\gamma}^(x')) \tag{1.4}
\end{array}
\right.$$
$$V^(x)=\mathop{max}{a \in A}Q^{\pi}(x,a)$$
带入公式（1.3）得到最优Bellmann等式，其唯一解是最优值函数
$$\left{\begin{array}{ll}Q_T^(x,a)=\sum{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}\mathop{max}{a' \in A}Q{T-1}^(x',a'))\
Q_\gamma^(x,a)=\sum_{x'\in X}P_{x \rightarrow x'}^a(R_{x \rightarrow x'}^a + \gamma \mathop{max}{a' \in A}Q{\gamma}^*(x',a'))\tag{1.5}
\end{array}
\right.$$
$$
\begin{equation}
\begin{array} {l}
V^\pi(x)&\leq Q^\pi(x,\pi'(x))\
&=\sum_{x'\in X}P_{x \rightarrow x'}^{\pi'(x)}(R_{x \rightarrow x'}^{\pi'(x)} + \gamma V^\pi(x'))\
&\leq\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}E_\pi[\frac{1}{T-1}\sum_{t=1}^{T-1}r_t|x_0=x'])\
&=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(\frac{1}{T}R_{x \rightarrow x'}^a + \frac{T-1}{T}V_{T-1}^\pi(x')) \
V_{\gamma}^\pi(x)&=\sum_{a\in A}\pi(x,a)\sum_{x'\in X}P_{x \rightarrow x'}^a(R_{x \rightarrow x'}^a + \gamma V_{\gamma}^\pi(x')) \tag{1.2}
\end{array}
\end{equation}$$