3 马尔科夫决策过程
-
状态转移矩阵 $cal(P)$,表示状态对转移概率,为方阵,第 $i$ 行第 $j$ 个表示 $s_i$ 转移到 $s_j$ 概率
MRP
- 下方 $s$ 表示状态集合中的元素,$S_t$ 表示某时刻状态取值
- $R_t$: 随机变量,$t$ 时刻获得的奖励
- $r(s)$: 转移到状态 s 获得的奖励的期望
- $G_t$: 一个马尔科夫过程中,从状态 $S_t$ 开始到无穷步后衰减奖励之和
- $gamma$: 这里引入了衰减系数,则有 $G_t = R_t + gamma R_(t + 1) + gamma^2 R_(t + 2).. = sum_(k = 0)^oo gamma^k R_(t + k)$
- $V(s)$: 价值函数, 为一个状态的期望回报 $= EE[G_t | S_t = s] = EE[R_t + gamma V(S_(t + 1)) | S_t = s] = r(s) + gamma sum_(s^prime in S) p(s^prime | s) V(s^prime)$
- 上一行等号最右边叫做贝尔曼方程,由 V 和邻接 V 组成
- $cal(V) eq.def [V(s_1) ... V(s_n)]^T$
- 奖励函数列向量 $cal(R)$ 由 $r(s_i)$ 组成
- 贝尔曼方程矩阵形式: $cal(V) = (I - gamma cal(P))^(-1) cal(R)$ 此法复杂度 $n^3$,不适用于大数据
MDP
- $A$:动作集合
- $r(s, a)$:期望奖励同时取决于状态和动作
- $P(s^prime | s, a)$ :状态转移概率也是,故马尔可夫矩阵不再有用
策略
- $pi(a | s)$:状态 $s$ 下采取 $a$ 的概率
- $V^pi (s) eq.def EE_pi [G_t | S_t = s]$ 状态价值函数 state-value function,即还不确定 $a$
- $Q^pi (s, a) = EE_pi [G_t | S_t = s, A_t = a]$ 动作价值函数 action-value function,即确定了 $a$
- 有 $V^pi (s) = sum_(a in A) pi(a | s) Q^pi (s, a)$
- 有 $Q^pi (s, a) = r(s,a) + gamma sum_(s^prime in S) P(s^prime | s, a) V^pi (s^prime)$
- $s -->^pi a_i -->^P s^prime$
贝尔曼期望方程
- 代入即可,要么由 V 和邻接 V 组成,要么由 Q 和邻接 Q 组成
- 将 $V^pi (s)$ 表示为关于下一个状态的等式
- 将 $Q^pi (s, a)$ 同样表示为关于下一个状态和动作的等式
- $A$ 和 $S$ 的例子
边缘化求状态价值函数
- 边缘化:将 MDP 转化为 MRP:状态期望奖励 = 所有动作奖励 $times$ 动作概率,$"状态转移到 s' 概率" = "所有动作转移到 s' 概率" times "动作概率"$
蒙特卡洛方法
- 随机采样若干条序列,计算统计回报
- 更新方法:先获得一个序列,对该序列从后往前计算
占用度量
- $nu_0 (s)$ : MDP 的初始状态分布,为一向量
- $P_t^pi (s)$ : 策略 $pi$ 下智能体 $t$ 时刻为状态 $s$ 的概率
- $nu^pi (s)$ : 状态访问分布,$nu^pi (s) = (1 - gamma) sum_(t = 0)^oo gamma^t P_t^pi (s)$ ,指策略下所有步在状态 $s$ 的概率的衰减加权和
- 性质(离散形式类似于 MDP 贝尔曼期望方程):
- $rho^pi (s, a) eq.def (1 - gamma) sum_(t = 0)^oo gamma^t P_t^pi (s) pi (a | s)$ : 占用度量,就是状态访问分布乘动作权重,表示策略下所有步在该(状态-动作对)的概率的衰减加权和
- 定理 1: 占用度量相同 $<==>$ 策略相同
- 定理 2: 合法占用度量 $rho$ ,可生成该占用度量的唯一策略为:
$$pi_rho (s, a) = rho(s, a) / (sum_(a^prime) rho(s, a^prime)) $$
最优策略
- 定理:有限状态和动作集合中,必然存在一个策略,在任意状态下的状态价值函数均不劣于其他策略
- 感性上确实能理解
- $V^(s), Q^(s, a)$ : ...
- 重要:$V^ (s) = max_(a in cal(A)) Q^(s, a)$,只需选最好的一个动作即可。这是一个循环依赖,需要解方程
贝尔曼最优方程
- 由上面导出