强化学习之Makov决策

离散时间Makov决策过程

离散时间的Markov决策过程模型可以在离散时间的智能体/环境接口的基础上进一步引入具有Markov性的概率模型得到。

奖励,汇报和价值函数

对于回合制任务，驾驶某一回合在第t步达到终止状态，则从步骤t(t<T)以后的回报（return）Gt可以定义为未来奖励的和：

Gt=Rt+1+Rt+2+…+Rt

但是对于连续性任务，上述Gt的定义会带来一些麻烦。由于连续性的任务没有终止时间，所以Gt会包括t时刻以后的所有奖励信息。但是如果这样对未来的信息进行求和，那么未来奖励信息的总和往往是无穷大的，为了解决这个问题，我们引入了折扣的概念：

∑

∞

G_t=R_t+{\gamma}R_{t+2}+{\gamma}^2R_{t+2}+{\gamma}^3R_{t+3}+…..=\sum_{

{\tau}=0}^{+\infty}{\gamma}^{\tau}R_{t+{\tau}+1}

$G_{t} = R_{t} + γ R_{t + 2} + γ^{2} R_{t + 2} + γ^{3} R_{t + 3} + . . . . . = τ = 0 \sum + \infty γ^{τ} R_{t + τ + 1}$

其中折扣因子γ∈[0,1]。折扣因子决定了如何在最近的奖励和未来的奖励间进行折中，若γ=0则注重面前的利益，若γ=1认为当前1单位的奖励和未来的1单位奖励是一样重要的。

注意：平均奖励：平均奖励定义为：

lim

⁡

→

∞

[

∑

]

\bar{R}=\lim_{t \to {+\infty}}E[\frac{1}{t}\sum_{\tau=0}^{t}R_{\tau}]

$\overset{ˉ}{R} = t \to + \infty lim E [\frac{1}{t} τ = 0 \sum t R_{τ}]$

是对除以步数的期望就极限的结果。还有相对于平均奖励的回报，及让每一步的奖励都减去平均奖励后再求回报。

基于回报的定义我们进一步定义价值函数：

状态价值函数：状态价值函数V

π

（s）表示从状态s开始采用策略

π

的预期回报。

(

)

[

∣

]

V_{\pi}(s)=E_{\pi}[G_t{\mid}S_t=s]

$V_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

动作价值函数：动作价值函数q

π

（s,a）表示在状态s采取动作a后，采用策略π的预期回报：

[

∣

]

q_{\pi}=E[G_t{\mid}S_t=s,A_t=a]

$q_{π} = E [G_{t} ∣ S_{t} = s, A_{t} = a]$

Bellman期望方程

策略评估则是试图求解给定策略的价值函数。Bellman期望方程常用来进行策略评估。

Bellman期望方程刻画了状态价值函数和动作价值函数之间的关系。该方程由以下两部分做成。

用t时刻的动作价值函数表示的t时刻的状态价值函数：

(

)

∑

(

∣

)

(

)

∈

V_{\pi}(s)=\sum_{a}{\pi}(a{\mid}s)q_{\pi}(s,a), s{\in}S

$V_{π} (s) = a \sum π (a ∣ s) q_{π} (s, a), s \in S$

用t+1时刻的状态价值函数表示的t时刻的动作价值函数：

(

)

(

)

∑

(

∣

)

[

(

)

]

∈

q_{\pi}(S,a)=r(s,a)+{\gamma}\sum_{s_{}^{,},r}p(s_{}^{,},r{\mid}s,a)[r+{\gamma}v_{\pi}(s_{}^{,})], s{\in}S,a{\in}A

$q_{π} (S, a) = r (s, a) + γ s_{,}, r \sum p (s_{,}, r ∣ s, a) [r + γ v_{π} (s_{,})], s \in S, a \in A$

在上式中利用带入法消除其中一种价值函数得到一些两种结果。

用状态价值函数表示状态价值函数

(

)

∑

(

∣

)

[

(

)

∑

(

∣

)

(

)

]

∈

V_{\pi}(s)=\sum_{a}{\pi}(a{\mid}s)[r(s,a),{\gamma}\sum_{s_{}^{,}}p(s_{}^{,}{\mid}s,a)v_{\pi}(s_{}^{,})], s{\in}S

$V_{π} (s) = a \sum π (a ∣ s) [r (s, a), γ s_{,} \sum p (s_{,} ∣ s, a) v_{π} (s_{,})], s \in S$

用动作价值函数表示动作价值函数

(

)

∑

(

∣

)

[

∑

(

∣

)

(

)

]

∈

q_{\pi}(s,a)={\gamma}\sum_{s_{}^{,},r}p(s_{}^{,},r{\mid}s,a)[r+\sum_{a_{}^{,}}{\pi}(a_{}^{,}{\mid}s_{}^{,})q_{\pi}(s_{}^{,},a_{}^{,})] s{\in}S,a{\in}A

$q_{π} (s, a) = γ s_{,}, r \sum p (s_{,}, r ∣ s, a) [r + a_{,} \sum π (a_{,} ∣ s_{,}) q_{π} (s_{,}, a_{,})] s \in S, a \in A$

最优策略及其性质

于

两

个

策

略

和

如

果

对

于

任

意

∈

都

有

(

)

(

)

则

称

策

略

小

于

等

于

记

作

。

这

就

是

最

优

策

略

。

对于两个策略\pi和\pi_{}^{,},如果对于任意s{\in}S,都有V_{\pi}(s)<V_{\pi^{,}}(s),则称策略\pi小于等于{\pi^{,}},记作{\pi}<{\pi^{,}}。这就是最优策略。

$对于两个策略 π 和 π_{,}, 如果对于任意 s \in S, 都有 V_{π} (s) < V_{π^{,}} (s), 则称策略 π 小于等于 π^{,}, 记作 π < π^{,} 。这就是最优策略。$

于

一

个

动

力

而

言

，

总

是

存

在

一

个

策

略

∗

使

得

所

有

的

策

略

都

小

于

等

于

这

个

策

略

。

这

时

，

策

略

∗

就

称

为

最

优

策

略

。

对于一个动力而言，总是存在一个策略{\pi_{*}},使得所有的策略都小于等于这个策略。这时，策略{\pi_{*}}就称为最优策略。

$对于一个动力而言，总是存在一个策略 π_{*}, 使得所有的策略都小于等于这个策略。这时，策略 π_{*} 就称为最优策略。$

最优策略的价值函数称为最优价值函数。最优价值函数包括以下两种形式。

最优状态价值函数

∗

(

)

{v_{*}(s)}

$v_{*} (s)$

公式,及

∗

max

⁡

(

)

∈

{v_{*}{s}=\max \limits_{\pi}v_{\pi}(s)} ,s{\in}S

$v_{*} s = π max v_{π} (s), s \in S$

最优动作价值函数，及

∗

(

)

max

⁡

(

)

∈

q_{*}(s,a)=\max _{\pi}q_{\pi}(s,a),s{\in}S,a{\in}A

$q_{*} (s, a) = π max q_{π} (s, a), s \in S, a \in A$

对于一个动力，可能存在多个最优策略。事实上，这些最优策略总是有相同的价值函数。所以，对于同时存在多个最优策略的情况下，任取一个最优策略来考察不失一般性。其中一种选取方法时选择这样的确定性策略：

∗

(

)

max

⁡

∈

∗

(

)

∈

\pi_{*}(s)=arg\max \limits_{a{\in}A}q_{*}(s,a),s{\in}S

$π_{*} (s) = a r g a \in A max q_{*} (s, a), s \in S$

其中如果有多个动作a使

∗

(

)

{q^{*}(s,a)}

$q^{*} (s, a)$

取得最大值，则任选一个动作即可。从这个角度来看，只有求得了最优价值函数，就可以直接得到一个最优策略。

Bellman最优方程

最优价值函数具有一个重要的性质–Bellman最优方程。Bellman最优方程可以用来求解最优价值函数。

策略的价值函数满足Bellman期望方程，最优价值函数也是如此。于此我们有了最优函数的性质

∗

(

∣

)

{

max

⁡

∈

∗

(

)

其

他

{\pi}_{*}(a{\mid}s)\left\{ \begin{array}{lr} 1 ,a=arg\max \limits_{a^{,}{\in}A}q_{*}(s,a^{,}) \\ 0,其他 \end{array} \right.

$π_{*} (a ∣ s) {1, a = a r g a^{,} \in A max q_{*} (s, a^{,}) 0, 其他$

带入Bellman期望方程，就可以得到Bellman最优方程。

于是我们有了最优状态价值函数表示最优状态价值函数

∗

(

)

max

⁡

∈

[

(

)

∑

(

∣

)

∗

(

)

]

∈

V_{*}(s)=\max \limits_{a{\in}A}[r(s,a)+{\gamma}{\sum_{s^{,}}}p(s^{,},r{\mid}s,a)v_{*}(s^{,})],s{\in}S

$V_{*} (s) = a \in A max [r (s, a) + γ s^{,} \sum p (s^{,}, r ∣ s, a) v_{*} (s^{,})], s \in S$

用最优动作价值函数表示最优动作价值函数

∗

(

)

(

)

∑

(

∣

)

max

⁡

∗

(

)

∈

q_{*}(s,a)=r(s,a)+{\gamma}{\sum_{s^{,}}}p(s^{,}{\mid}s,a)\max \limits_{a^{,}}q_{*}(s^{,},a^{,}),s{\in}S,a{\in}A

$q_{*} (s, a) = r (s, a) + γ s^{,} \sum p (s^{,} ∣ s, a) a^{,} max q_{*} (s^{,}, a^{,}), s \in S, a \in A$

悬崖寻路实例

import gym
import numpy as np
import scipy
def play_once(env,policy):

    total_reward=0
    state=env.reset()
    loc=np.unravel_index(state,env.shape)
    print("状态={},位置={}".format(state,loc))
    while True:
        env.render()
        action=np.random.choice(env.nA,p=policy[state])
        next_state,reward,done,_=env.step(action)
        print("状态={},位置={},奖励={}".format(state,loc,reward))
        total_reward+=reward
        if done:
            break
        state=next_state
    return total_reward
def evaluate_bellman(env, policy, gamma=1.):
    a, b = np.eye(env.nS), np.zeros((env.nS))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            pi = policy[state][action]
            for p, next_state, reward, done in env.P[state][action]:
                a[state, next_state] -= (pi * gamma)
                b[state] += (pi * reward * p)
    v = np.linalg.solve(a, b)
    q = np.zeros((env.nS, env.nA))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            for p, next_state, reward, done in env.P[state][action]:
                q[state][action] += ((reward + gamma * v[next_state]) * p)
    return v, q
def optimal_bellman(env, gamma=1.):
    p = np.zeros((env.nS, env.nA, env.nS))
    r = np.zeros((env.nS, env.nA))
    for state in range(env.nS - 1):
        for action in range(env.nA):
            for prob, next_state, reward, done in env.P[state][action]:
                p[state, action, next_state] += prob
                r[state, action] += (reward * prob)
    c = np.ones(env.nS)
    a_ub = gamma * p.reshape(-1, env.nS) - \
            np.repeat(np.eye(env.nS), env.nA, axis=0)
    b_ub = -r.reshape(-1)
    a_eq = np.zeros((0, env.nS))
    b_eq = np.zeros(0)
    bounds = [(None, None),] * env.nS
    res = scipy.optimize.linprog(c, a_ub, b_ub, bounds=bounds,
            method='interior-point')
    v = res.x
    q = r + gamma * np.dot(p, v)
    return v, q


env=gym.make("CliffWalking-v0")
print("观测空间={}".format(env.observation_space))
print("动作空间={}".format(env.action_space))
print("状态数量={},动作数量={}".format(env.nS,env.nA))
print("地图大小={}".format(env.shape))
# #最优策略
# actions=np.ones(env.shape,dtype=int)
# actions[-1,:]=0
# actions[:,-1]=2
# optimal_policy=np.eye(4)[actions.reshape(-1)]
# total_reward=play_once(env,optimal_policy)
# print("总奖励={}".format(total_reward))

optimal_state_values, optimal_action_values = optimal_bellman(env)
print('最优状态价值 = {}'.format(optimal_state_values))
print('最优动作价值 = {}'.format(optimal_action_values))
optimal_actions = optimal_action_values.argmax(axis=1)
print('最优策略 = {}'.format(optimal_actions))

原文链接：https://blog.csdn.net/qq_51324662/article/details/120172657