Markov decision processes(MDP)
MDP(s, A, { $P_{sa}$}, $\gamma$, R)
- s是状态集合
- A是动作集合
- 给定一个状态s和动作a, $P_{sa}$代表在s状态下采取a状态转移概率分布
- $\gamma \in [0,1)$表示折现系数/折扣率
- $R: S \times A \mapsto 实数集合$是回报函数(reward function)
Total payoff
我们的目标是
Policy 是函数 $\pi: S \mapsto A$,定义它的 Value function是
给定一个policy $\pi$,它的value function满足Bellman方程
定义optimal value function是
那么相对应的最优策略(optimal policy)是
求解的算法有以下几种。
Value Iteration
- $V(s) = 0$
- 对每个状态s,更新
重复直到收敛 - 得到 $V^(s)$ 之后用(2)式求解 $\pi^ (s)$
Policy Iteration
- 随机初始化 $\pi$
- $V := V^{\pi}$ (通过解Bellman方程(1)组,适用于状态少的情况)
- $\pi(s) := \underset{a}{argmax}\;\sum_{s’}P_{sa}(s’)V(s’)$
- 重复2.3直到收敛
Continous state MDPs
当状态是连续空间/无限个状态,动作集合是离散空间时,我们假设有一个MDP的模型或者仿真器:输入s,a,这个模型输出状态 $s’ \sim P_{sa}$
这样的模型分为两种：决定性( $e.g. s_{t+1} = As_{t}+Ba_{t}$)和随机的 ( $e.g.s_{t+1} = As_{t}+Ba_{t} + \varepsilon_t$)
我们需要对 $V$的一个好的估计使得便于计算/对于没在训练集出现过的状态也能很好的预测/即使训练集只是状态全集的一部分也能很好的估计 $V$
Fitted value iteration
选择
来估计
Repeat{
- 随机抽样 { $s^1, s^2, …, s^m$}
- 初始化 $\theta = 0$
- 重复下面过程(对真实值的近似,想要 $y^i \thickapprox V(s^i)$)
- 对每一个样本 $s^i$，对每个动作 $a$
- 按照 $P_{s^ia}$的分布抽样得 $s_1’,\ldots,s_k’$
- 令 $q(a) = \frac{1}{k}\sum_{i=1}^k [R(s^i) + \gamma V(s_j’)]$
- $y^i = \underset{a}{\mathrm{max}}\;q(a)$
- $\theta := \underset{\theta}{\mathrm{argmin}}\;\sum{(\theta^T\phi(s^i) - y^i)^2}$ (希望用 $\theta$的估计值和真实值接近)
}
同样地, $\pi^* (s) = \underset{a}{\mathrm{argmax}}\;E_{s’\sim P_{sa}[V^*(s’)]}$
state-action Reward
Total payoff:
求解optimal value function
value iteration算法和之前的一样
Finite horizon MDPs
$(S,A,\{P_{sa}^{(t)}\},T,R)$
其中 $T$是horizon time, $s_{t+1} \sim P_{s_t a_t}^{(t)}$
Total payoff:
求解目标:
Dynamic programming algorithm
- $V_T^*(s) = \underset{a}{\mathrm{max}}\;R^{(T)}(s,a)$
-
from T to 1:
- from T to 0:
Linear Quadratic Regulator
基于很强的假设,但往往是有用的
对于finite horizon MDP,其中 $s \in \mathbb{R}^n$, $a \in \mathbb{R}^d$
Assumption:
$P_{sa}^{(t)}:$ $s_{t+1} = A_t s_t + B_t a_t + w_t \quad w_t \sim N(0, \Sigma_w)$
其中 $A_t \in \mathbb{R}^{n \times n}, B_t \in \mathbb{R}^{n \times d}$
$R^{(t)}(s_t,a_t) = -(s_t^T U_t s_t + a_t^T V_t a_t) \quad U_t \ge 0 \; V_t \ge 0$
其中 $U_t \in \mathbb{R}^{n \times n}, V_t \in \mathbb{R}^{d \times d}$,也就是说reward是非正数
LQR有如下性质:
假设 $V_{t+1}$有如下形式
那么 $V_t^* (s_t) = \underset{a_t}{\mathrm{max}}\;R^{(t)}(s_t,a_t) + \underset{s_{t+1} \sim P_{s_t,a_t}}{E}[V_{t+1}^* (s_{t+1})]$
可以证明 $V_t$ 可以写成同样的形式
用动态规划算法求解问题
首先
由此可以推出 $V_{T-1}$…
递推公式是
对应的最优策略为
可以看出最优策略和 $\Sigma_w$无关
Linearize a non-linear function
对于状态 $s_{t+1}$是 $s_t,a_t$的非线性函数,我们可以在某一个点附近用它的线性展开近似函数值
Differential dynamic programming
$s_{t+1} = f(s_t,a_t)$ ,f是非线性函数,确定性的状态转移
(1)有正常轨迹 $\bar{s_0},\bar{a_0},\cdots,\bar{s_T},\bar{a_T}$
(2)在 $(s_t,a_t)$点附近线性化f
(3)用LQR得到 $\pi_t$
(4)用仿真器得到新的轨迹 重复上述过程
