温馨提示:如果您当前是小程序版页面,由于小程序端对Markdown和latex语法暂时不支持,该文章可能会出现乱码,请用浏览器访问:

一个人de博客

概要

优点

Q-Learning算法是强化学习领域一个特别经典的算法,其具有系统行为无关和易于实现的特点。

局限性

就个人理解来看,其最主要的缺点在于对于系统状态数目几乎无限或者说较多的情况下,该算法显得较为无力。

Q值函数

Q函数是一个可以用表格形式描述的离散函数,表格的行数等于系统的状态数目,列数等于agent在系统中可采取的动作总数,有时候我们也称其为Q矩阵,直观形式如下:

搜狗截图20181219090211.png
搜狗截图20181219090211.png

其中的每个元素Q(Si,ai)表示当agent处于状态Si时,执行了动作ai以后能够获得的期望回报值。也因此Q-learning的目标通过与系统交互,根据系统的回馈,不断迭代修改Q矩阵中值,以使得Q矩阵达到一种稳定状态,即可利用Q-矩阵评价每种状态下采取每种动作所能获得的期望回报值。

算法流程

上面引出了Q-矩阵的定义以及意义,那么还有两个问题需要讨论:
1.Q-矩阵如何迭代,其中的元素如何修改;
2.Q-矩阵如何指导agent的行为;

Q-矩阵如何指导agent的行为

先讨论问题二,关于Q-矩阵如何指导agent行为的问题,该问题可以转化为agent如何根据Q-矩阵并结合自己当前所处的状态决策出自己将要采用的动作,这就引出了ε-greedy策略,在具体介绍该策略之前,我们先考虑贪心策略,即每次都选取期望回报值最大的动作,这听起来似乎很有道理,但仔细一想,却有那么一丝丝瑕疵,古往今来,伟大的先哲们告诉我们,参考过去的经验是合理的,但适当的探索是必要的,如果拘泥于过去的经验,只会停滞不前,难以取得进步,Q-矩阵在这里就相当于agent与系统交互迭代过程中所积累的丰富的历史经验。而ε-greedy策略可以说是“经验”与“探索”的平衡策略,其核心思想较为简单:

    事先选取一个范围为(0,1)的ε值,如ε=0.1,在agent动作决策时,产生一个(0,1)之间的随机数,如果该随机数小于ε,则随机选取一个动作(探索),否则根据Q-矩阵选取最大的回报值对应的动作(经验),即10%的概率进行探索型操作,90%的概率进行经验型操作。

Q-矩阵如何迭代

下面进入一个最核心问题的讨论,即Q-矩阵的迭代。Q-矩阵是在与系统交互的过程中,根据系统的回馈对Q-矩阵进行修正,这个交互学习的过程,就称之为Q-Learning过程,大致流程图:

图片1_看图王.png
图片1_看图王.png

嗯。。。那个流程图中的‘是’和‘否’反了,要注意(为啥博主不改一下?博主较懒。。。),其中根据回报值更新Q-矩阵的部分,具体按照如下公式更新:
图片2.png
图片2.png

其中s为决策时所处的状态,a为采取的动作,s'为执行动作后达到的新状态,γ为衰减系数,α为学习率,两者范围均为(0,1),reward为系统给出的即时回报值。

算法收敛性证明

emmmm。。。这一部分略过,各位看官其实也不特别关心,证明过程过长,大家可以参看Q-Learning收敛性证明的相关论文。

算法具体应用与实现

下面给出一个有趣的应用,一个Q-learning算法指导agent更快找到迷宫中糖果的示例,迷宫地图如下:

..........
.  x     .
.   x o  .
.        .
.    x   .
..........

x代表陷阱,若agent到达x所在的位置,agent会受到扣除5分的惩罚,o为糖果,若agent找到糖果,agent会得到100分的奖赏,对agent的期望很简单,在避开陷阱的情况下,以最少的移动次数找到糖果。具体实现如下:
迷宫测试环境的模拟实现:

from __future__ import print_function
import copy


# MAP = \
#     '''
# .........
# .       .
# .     o .
# .       .
# .........
# '''

MAP = \
    '''
..........
.  x     .
.   x o  .
.        .
.    x   .
..........
'''
MAP = MAP.strip().split('\n')
MAP = [[c for c in line] for line in MAP]


DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]


class Env(object):
    def __init__(self):
        self.map = copy.deepcopy(MAP)
        self.x = 1
        self.y = 1
        self.step = 0
        self.total_reward = 0
        self.is_end = False

    def interact(self, action):
        assert self.is_end is False
        new_x = self.x + DX[action]
        new_y = self.y + DY[action]
        new_pos_char = self.map[new_x][new_y]
        self.step += 1
        if new_pos_char == '.':
            reward = 0  # do not change position
        elif new_pos_char == ' ':
            self.x = new_x
            self.y = new_y
            reward = 0
        elif new_pos_char == 'o':
            self.x = new_x
            self.y = new_y
            self.map[new_x][new_y] = ' '  # update map
            self.is_end = True  # end
            reward = 100
        elif new_pos_char == 'x':
            self.x = new_x
            self.y = new_y
            self.map[new_x][new_y] = ' '  # update map
            reward = -5
        self.total_reward += reward
        return reward

    @property
    def state_num(self):
        rows = len(self.map)
        cols = len(self.map[0])
        return rows * cols

    @property
    def present_state(self):
        cols = len(self.map[0])
        return self.x * cols + self.y

    def print_map(self):
        printed_map = copy.deepcopy(self.map)
        printed_map[self.x][self.y] = 'A'
        print('\n'.join([''.join([c for c in line]) for line in printed_map]))

    def print_map_with_reprint(self, output_list):
        printed_map = copy.deepcopy(self.map)
        printed_map[self.x][self.y] = 'A'
        printed_list = [''.join([c for c in line]) for line in printed_map]
        for i, line in enumerate(printed_list):
            output_list[i] = line

Q-learning:

from __future__ import print_function
import numpy as np
import time
from env import Env
import matplotlib.pyplot as plt


EPSILON = 0.1
ALPHA = 0.1
GAMMA = 0.9
MAX_STEP = 30

np.random.seed(0)

def epsilon_greedy(Q, state):
    if (np.random.uniform() > 1 - EPSILON) or ((Q[state, :] == 0).all()):
        action = np.random.randint(0, 4)  # 0~3
    else:
        action = Q[state, :].argmax()
    return action


e = Env()
Q = np.zeros((e.state_num, 4))
rewards=[]
steps=[]
for i in range(300):
    e = Env()
    while (e.is_end is False) and (e.step < MAX_STEP):
        action = epsilon_greedy(Q, e.present_state)
        state = e.present_state
        reward = e.interact(action)
        new_state = e.present_state
        Q[state, action] = (1 - ALPHA) * Q[state, action] + \
            ALPHA * (reward + GAMMA * Q[new_state, :].max())
        e.print_map()
        time.sleep(0.05)
    print('Episode:', i, 'Total Step:', e.step, 'Total Reward:', e.total_reward)
    rewards.append(e.total_reward)
    steps.append(e.step)
    time.sleep(0.02)
plt.plot(rewards)
plt.plot(steps,color='red')
plt.show()

迭代曲线如图所示:

搜狗截图20181218215101.png
搜狗截图20181218215101.png

根据蓝线所示的分数趋势,可以看到agent的分数大概在经过50步迭代以后趋于稳定,即100分左右徘徊;并且可以看到红线所示的移动次数变化趋势,agent的移动次数也趋于稳定,大概经过8次移动就能找到糖果。