RL

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

強化學習任務通常用馬爾科夫決策過程(Markov Decision Process,簡稱 MDP)來描述：

機器處于環(huán)境$E$中沼填，狀態(tài)空間為$X$,其中每個狀態(tài)$x \in X$是機器感知到的環(huán)境的描述桅咆，機器能采取的動作構(gòu)成了動作空間$A$，若某個動作$a\in A$作用在當前狀態(tài)$x$上坞笙，則潛在的轉(zhuǎn)移函數(shù)$P$將使得環(huán)境從當前狀態(tài)按某種概率轉(zhuǎn)移到一另個狀態(tài)岩饼，在轉(zhuǎn)移到另一個狀態(tài)的同時，環(huán)境會根據(jù)潛在的獎賞（reward）函數(shù)$R$反饋給機器一個獎賞薛夜。綜合起來籍茧，強化學習任務對應了四元組$E=<X,A,P,R>$,其中$P:X\times A\times X \mapsto \mathbb{R}$指定了狀態(tài)轉(zhuǎn)移概率,$R:X \times A \times X \mapsto \mathbb{R}$指定了獎賞，在有的應用中梯澜，獎賞函數(shù)可能僅與狀態(tài)轉(zhuǎn)移有關(guān)寞冯，即$R: X \times X \mapsto \mathbb{R}$.

在環(huán)境中狀態(tài)的轉(zhuǎn)移，獎賞的返回是不受機器控制的，機器只能通過選擇要執(zhí)行的動作來影響環(huán)境吮龄，也只能通過觀察轉(zhuǎn)移后的狀態(tài)和返回的獎賞來感知環(huán)境檬某。
策略（policy）$\pi$的定義,根據(jù)這個策略，在狀態(tài)$x$下就能得知要執(zhí)行的動作$a=\pi(x)$螟蝙，確定性動作表示為$\pi:X \mapsto A$,隨機性動作表示為$\pi:X\times A \mapsto \mathbb{R}$，$\pi(x,a)$為狀態(tài)$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：很好的估計每個要比的獎賞喧半，失去選擇最優(yōu)搖臂的機會
exploitation-only：沒有很好估計搖臂期望獎賞奴迅，很可能選不到最優(yōu)的搖臂
因為嘗試次數(shù)有限，加強了一方則會削弱另一方挺据，面臨“探索-利用窘境”(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

對于離散狀態(tài)空間,離散動作空間上的多不講話學習人物王暗，一種直接的辦法是將每個狀態(tài)上動作的選擇看做一個$K$-搖臂賭博機問題悔据，用強化學習任務的累計獎賞來代替$K$-搖臂賭博機算法中的獎賞函數(shù)，即可將賭博計算法用于每個狀態(tài)

有模型學習###

$$E=<X,A,P,R>$$
機器已對模型進行了建模俗壹，能在機器內(nèi)部模擬出與環(huán)境相同活近似的狀況科汗，對于任意狀態(tài)$x,x'$和動作$a$,在$x$狀態(tài)下執(zhí)行動作$a$轉(zhuǎn)移到$x'$狀態(tài)的概率$P_{x \rightarrow x'}^a$是已知的，改轉(zhuǎn)移所帶來的獎賞$R_{x \rightarrow x'}^a$也是已知的
$V^\pi(x)$表示從$x$出發(fā)策肝，使用策略$\pi$所帶來的累積獎賞."狀態(tài)值函數(shù)"(state value function)
$Q^\pi(x,a)$表示從$x$出發(fā)肛捍，執(zhí)行動作$a$后再使用策略$\pi$帶來的累積獎賞."狀態(tài)-動作值函數(shù)"(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已知，才能進行全概率展開之众，類似于動態(tài)規(guī)劃
停止準則拙毫，設(shè)置一個閾值$\theta$滿足值函數(shù)的改變在一次迭代后改變小于$\theta$則停止$\max_{x\in X}|V(x)-V'(x)|<\theta$
通過狀態(tài)值函數(shù)V，就能直接計算出狀態(tài)-動作值函數(shù)
$$\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.$$

策略改進####

對某個策略的累計獎賞進行評估后棺禾，若發(fā)現(xiàn)它并非最有策略缀蹄，則希望改進。理想的策略應能最大化累積獎賞
$$\pi^=\mathop{argmax}\pi\sum{x\in X}V^\pi(x)$$
一個強化學習任務可能有多個最優(yōu)策略，最有策略所對應的值函數(shù)$V^$稱為最優(yōu)值函數(shù)缺前，即
$$\forall x \in X:V^*(x)=V{\pi^}(x)$$
策略空間是所有狀態(tài)上所有動作的組合蛀醉，共有$|A|^{|X|}$種不同的策略
將動作的求和改為取最優(yōu)，公式(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）得到最優(yōu)Bellmann等式衅码，其唯一解是最優(yōu)值函數(shù)
$$\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}$$