Created by potrace 1.13, written by Peter Selinger 2001-2015

强化学习

强化学习是介于监督学习与非监督学习之间的一种学习.这么说的原因是因为,强化学习所用的数据并没有标记,所以它不是监督学习.如果说它是非监督学习也不正确,因为它有所有的奖励函数对结果进行反馈,这也可以算是一种监督,但相比标记数据的监督要少的多.

比如训练AI学习下棋,我们不知道下在什么地方才是好棋,但是可以根据结果的胜负来做奖励或者惩罚,随着时间的推移,它会做的越来越好.就好比训练一只狗,当它做的好奖励它,做的不好的时候惩罚它,狗会学会做越来越多好的事.

马尔可夫决策过程 (MDP)

马尔可夫决策过程包含这样几个元素 (S, A, \{P_{sa}\}, γ, R) , 其中:

举个简单的例子,想象一下一个机器人生活在一个网格的世界里,阴影是障碍物.机器人想要到达右上角,使用+1作为奖励,并且机器人要避免到达-1的位置.

image

在这个例子中,机器人一共有11个可能的位置所以它有11个状态:
S = \{(1,1),(1,2)....\}

机器人可以向四个方向运动,所以它的动作集合为:
A = \{N,S,E,W\}

当我们命令机器人向前走的时候,由于噪声等原因,机器人有一定的概率没有向前走,而是像左或者右走:

image

假设机器人现在在(3,1)位置上,如果用状态转移概率来描述的话为:
P_{(3,1),N}((3,2)) = 0.8
P_{(3,1),N}((4,1)) = 0.1
P_{(3,1),N}((2,1)) = 0.1
P_{(3,1),N}((3,3)) = 0
\qquad \vdots

再来看一下奖励函数,为了让机器人以最快的方式到达目的,我们要收取机器人的燃油费:
R((4,3)) = +1
R((4,2)) = -1
R(s) = -0.02

在机器人开始运动的时候,首先我们会选择一个初始状态 s_0 ,然后再选择一个动作 a_0 ,随后你会的到一个新的状态 s_1 \sim P_{s_0a_0} ,接下来再选择一个动作 a_1 ,随后又得到一个新的状态 s_2 \sim P_{s_1a_1}

image

我们把每个状态使用奖励函数,得到总的奖励:

R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...

这里的 \gamma 是折扣因子,因为前面的动作会影响整个后面的动作,所以前面决策的正确与否影响更大,所以给与的奖励更多.

强化学习的目标就是让总奖励的期望最大化:
E[R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...]

假设我们现在的状态为s,我们通过带入函数就可以的到下一步a的状态, a=\pi(s) ,那么我们把这个函数 \pi 称为策略函数.

value function

我们定义值函数:
V^\pi(s) = E[R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...| s_0 = s,\pi]

例如下面是对应 \pi 的值函数分布:

image

我们对值函数进行一下变形:
V^\pi(s) = E[R(s_0)+\gamma (R(s_1)+\gamma R(s_2)+...)| s_0 = s,\pi]

其中 R(s_1)+\gamma R(s_2)+... 相当于 V^\pi(s') ,所以值函数又可以写为:

V^\pi(s) = R(s)+\gamma \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

其中添加 \sum_{s'} P_{s\pi(s)}(s') 的原因是 s' 是个随机变量,所以需要计算一下概率. P_{s\pi(s)}(s') 表示从 s 到 s' 的概率.

这个方程叫做贝尔曼方程.

举个例子,假设现在小车在(3,1)位置,且 \pi((3,1)) = N :

image

V^\pi((3,1)) = R((3,1))+\gamma [0.8V^\pi((3,2))+0.1V^\pi((4,1))+0.1V^\pi((2,1))]

我们定义最优值函数为:
V^*(s) = max_\pi V^\pi(s)

即:
V^*(s) = R(s) + max_a \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

由此我们可以得出最佳测量函数 \pi^*(s) 的定义:
\pi^*(s) = arg \; max_a \sum_{s'} P_{sa}(s')V^\pi(s')

值迭代算法

first-step,初始化:

V(s) = 0

例如上面机器人的例子,就是创建一个11个元素的数组.

second-step,循环每一个状态,计算每个状态的值,也就对11状态调用最优值函数:

V(s) := R(s) + max_a \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

当运行完算法之后, V(s) 会收敛到 V^*(s) ,下面是算法得到的 V(s) :

image

你已经知道该如何走了对么,每次只要向着更大的V(s)走就对了.这里有人可能会疑惑,在位置(3,1)看起来向N走更近一些啊,不要忘了机器人有一定几率走偏,那么它有可能走向-1,所以它采取了更为稳健的方式.

策略迭代算法

first-step,随机初始化策略函数 \pi() ,就像这样:

image

second-step,循环下面两步:
V := V^\pi
\pi(s) := arg \; max_a \sum_{s'} P_{sa}(s')V(s')

当运行完算法之后, \pi(s) 会收敛到 \pi^*(s)

估计 P_{sa}

回顾一下MDP中的5个元素, (S, A, \{P_{sa}\}, γ, R) ,其中 S, A, γ, R ,我们都可以得到,但是 P_{sa} 通常情况我们是事先不知道的.所以需要通过数据估计 P_{sa} .

posted @ 2018-09-05 17:33:12
评论加载中...
发表评论