强化学习中，“模型”通常指与智能体交互的环境模型，即对环境的状态转移概率和奖励函数进行建模。根据是否具有环境模型，强化学习算法分为两种：
本文的主角 Dyna-Q 算法也是非常基础的基于模型的强化学习算法，不过它的环境模型是通过采样数据估计得到的。
强化学习算法有两个重要的评价指标：
基于模型的强化学习算法由于具有一个环境模型，智能体可以额外和环境模型进行交互，对真实环境中样本的需求量往往就会减少，因此通常会比无模型的强化学习算法具有更低的样本复杂度。但是，环境模型可能并不准确，不能完全代替真实环境，因此基于模型的强化学习算法收敛后其策略的期望回报可能不如无模型的强化学习算法。
说到这里，我们思考如下两个问题：
Dyna-Q选手给出了它的答案，把基于模型 + 不基于模型的强化学习结合起来，它既在模型中学习，也在交互中学习。下面就来看看Dyna-Q算法的一些思想吧。
Dyna-Q 算法是一个经典的基于模型的强化学习算法。Dyna-Q 使用一种叫做 Q-planning 的方法来基于模型生成一些模拟数据，然后用模拟数据和真实数据一起改进策略。Q-planning 每次选取一个曾经访问过的状态
s
s
s，采取一个曾经在该状态下执行过的动作
a
a
a，通过模型得到转移后的状态
s
′
s'
s′以及奖励
r
r
r，并根据这个模拟数据
(
s
,
a
,
r
,
s
′
)
(s,a,r,s')
(s,a,r,s′)，用 Q-learning 的更新方式来更新动作价值函数。
Dyna-Q算法简单明了，在算法的前面和普通的Q-learning算法一模一样，只有后面有所不同，见下面的Dyna-Q算法流程。下面的红框中的步骤①的前提是环境的模型是基于确定环境下的假设（对于非确定的环境或者是非常复杂的环境根据特定的情况来做假设），后面的步骤可以被概括为使用已经学习到的模型来更新Q函数
n
n
n次。最后的Q函数更新和前面的一模一样。此外，在Dyna-Q中同样的强化学习方法既可以用于从实际经验中学习也可以用于从模拟经验中进行规划，因此该强化学习方法是学习和规划的最终共同道路。
可以看到，在每次与环境进行交互执行一次 Q-learning 之后，Dyna-Q 会做 n n n次 Q-planning。其中 Q-planning 的次数 N N N是一个事先可以选择的超参数，当其为 0 时就是普通的 Q-learning。值得注意的是，上述 Dyna-Q 算法是执行在一个离散并且确定的环境中，所以当看到一条经验数据 ( s , a , r , s ′ ) (s,a,r,s') (s,a,r,s′)时，可以直接对模型做出更新，即 M ( s , a ) ← r , s ′ M(s, a) \leftarrow r, s^{\prime} M(s,a)←r,s′。
上图为Dyna-Q的结构。我们不难发现有两个向上的箭头指向 Policy/value functions，也就是我们这篇文章中说的Q function，左边的箭头是RL直接从实际的经验对Q进行更新，右边的更新Q箭头是从模拟经验进行的规划更新。由此可见，每当agent采取一个action时，学习的进程同时通过实际的选择的action和环境模型的模拟来更新，这样就能够加快我们智能体的学习速度。
代码实现如下：（其实和QL差不多，只是多了一点步骤）
import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm
import random
import gym
class DynaQ:
def __init__(self, ncol, nrow, epsilon, alpha, gamma, n_planning, n_action=4) -> None:
self.q_table = np.zeros([nrow * ncol, n_action]) # 初始化Q(s,a)表格
self.n_action = n_action
self.alpha = alpha
self.gamma = gamma
self.epsilon = epsilon
self.n_planning = n_planning
self.model = dict() # 环境模型
def select_actions(self, state):
if np.random.random() < self.epsilon:
action = np.random.randint(self.n_action)
else:
action = np.argmax(self.q_table[state])
return action
def QL_update(self, s, a, r, s_):
'''Q-learning算法更新步骤'''
td_error = r + self.gamma * self.q_table[s_].max() - self.q_table[s, a]
self.q_table[s, a] += self.alpha * td_error
def update(self, s, a, r, s_):
self.QL_update(s, a, r, s_)
################################################################
self.model[(s, a)] = r, s_ # 将数据添加到模型中
for _ in range(self.n_planning): # Q-planning循环
# 随机选择曾经遇到过的状态动作对
(s, a), (r, s_) = random.choice(list(self.model.items()))
self.QL_update(s, a, r, s_)
################################################################
def DynaQ_CliffWalking_running(self, num_episodes):
return_list = []
for i in range(10): # 显示10个进度条
with tqdm(total=num_episodes//10, desc=f"Iteration {i}") as pbar:
for ep in range(num_episodes//10): # 每个进度条的序列数
episode_return = 0
state = env.reset()
done = False
while not done:
action = agent.select_actions(state)
next_state, reward, done, _ = env.step(action)
episode_return += reward
agent.update(state, action, reward, next_state)
state = next_state
return_list.append(episode_return)
if (ep + 1) % 10 == 0:
pbar.set_postfix({
"episode": f"{i / 10 * i + ep + 1}",
"return": f"{np.mean(return_list[-10:])}"
})
pbar.update(1)
return return_list
def moving_average(a, window_size):
"""滑动平均"""
cumulative_sum = np.cumsum(np.insert(a, 0, 0))
middle = (cumulative_sum[window_size:] - cumulative_sum[:-window_size]) / window_size
r = np.arange(1, window_size - 1, 2)
begin = np.cumsum(a[:window_size - 1])[::2] / r
end = (np.cumsum(a[:-window_size:-1])[::2] / r)[::-1]
return np.concatenate((begin, middle, end))
if __name__ == '__main__':
env = gym.make("CliffWalking-v0")
n_row, n_col = env.shape
epsilon = 0.01
alpha = 0.1
gamma = 0.9
num_episodes = 300
n_planning_list = [0, 2, 20]
for n_planning in n_planning_list:
print('Q-planning步数为：%d' % n_planning)
agent = DynaQ(n_col, n_row, epsilon, alpha, gamma, n_planning)
return_list = agent.DynaQ_CliffWalking_running(num_episodes)
episodes_list = list(range(len(return_list)))
episodes_list = moving_average(episodes_list, 19)
plt.plot(episodes_list, return_list, label=str(
n_planning) + ' planning steps')
plt.legend()
plt.ylim(-250, 0)
plt.xlabel('Episodes')
plt.ylabel('Returns')
plt.title('Dyna-Q on {}'.format('Cliff Walking'))
plt.show()
代码运行结果如下：
从上述结果中我们可以很容易地看出，随着 Q-planning 步数的增多，Dyna-Q 算法的收敛速度也随之变快。当然，并不是在所有的环境中，都是 Q-planning 步数越大则算法收敛越快，这取决于环境是否是确定性的，以及环境模型的精度。在上述悬崖漫步环境中，状态的转移是完全确定性的，构建的环境模型的精度是最高的，所以可以通过增加 Q-planning 步数来直接降低算法的样本复杂度。
\quad
\quad
\quad
参考：
持续更新…