Provably Efficient Reinforcement Learning with Linear Function Approximation

1. Introduction

2. Preliminaries

考虑的是 Finite-horizon Episodic MDP $\mathrm{MDP}(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$，分别代表状态集合、动作集合、每个 episode 的长度。$\mathbb{P}=\{{\mathbb{P}}_h{\}}_{h=1}^H$ 和 $r=\{r_h{\}}_{h=1}^H$ 分别是分步/Time-inhomogeneous 的状态转移核与奖励函数。假设 $\mathcal{S}$ 是可测空间、$\mathcal{A}$ 是有限集合，且 $|\mathcal{A}|=A$。对每个 $h\in [H]$，${\mathbb{P}}_h(\cdot \mid x,a)$ 表示在第 $h$ 步、状态为 $x$、采取动作 $a$ 时对下一状态的转移分布；$r_h:\mathcal{S}\times \mathcal{A}\to [0,1]$ 是第 $h$ 步的确定性奖励函数。这里奖励函数可以是随机的，本文的结果可以泛化到这种情形。

智能体与该分幕 MDP 的交互过程如下：在每一幕，初始状态 $x_1$ 对抗性地随机指定，随后对每个时间步 $h\in [H]$，智能体观察到状态 $x_h\in \mathcal{S}$，选择动作 $a_h\in \mathcal{A}$ 并获得奖励 $r_h(x_h,a_h)$，环境按照概率测度 ${\mathbb{P}}_h(\cdot \mid x_h,a_h)$ 采样产生新状态 $x_{h+1}$。当到达 $x_{H+1}$ 时本幕结束，不再获得奖励。

策略 $\pi$ 是函数 $\pi :\mathcal{S}\times [H]\to \mathcal{A}$，其中 $\pi (x,h)$ 表示在第 $h$ 步处于状态 $x$ 时所采取的动作。由于在每一个时间步对应的动作价值函数和价值函数都不同，因此必须考虑每一个时间步对应的策略。对应的是价值函数和动作价值函数

$$\begin{array}{rl}{V}_h^{\pi }(x)& :=\mathbb{E}\left[\sum _{h^{\prime }=h}^H{r}_{h^{\prime }}(x_{h^{\prime }},\pi (x_{h^{\prime }},h^{\prime }))\mid x_h=x\right],\forall x\in \mathcal{S},h\in [H].\\ Q_h^{\pi }(x,a)& :=r_h(x,a)+\mathbb{E}\left[\sum _{h^{\prime }=h+1}^H{r}_{h^{\prime }}(x_{h^{\prime }},\pi (x_{h^{\prime }},h^{\prime }))\mid x_h=x,a_h=a\right],\forall (x,a)\in \mathcal{S}\times \mathcal{A},h\in [H].\end{array}$$

由于动作空间和幕长度都有限，因此一定存在一个最优策略 ${\pi }^{\star }$ 使得 $V_h^{\star }(x)={\sup }_{\pi }{V}_h^{\pi }(x)$ 对所有 $x,h$ 成立。使用 $[{\mathbb{P}}_h{V}_{h+1}](x,a):={\mathbb{E}}_{x^{\prime }\sim {\mathbb{P}}_h(\cdot \mid x,a)}[V_{h+1}(x^{\prime })]$，策略 $\pi$ 的 Bellman 方程写作

$$\begin{array}{r}{Q}_h^{\pi }(x,a)=(r_h+{\mathbb{P}}_h{V}_{h+1}^{\pi })(x,a),V_h^{\pi }(x)=Q_h^{\pi }(x,{\pi }_h(x)),V_{H+1}^{\pi }(x)=0\\ Q_h^{\star }(x,a)=(r_h+{\mathbb{P}}_h{V}_{h+1}^{\star })(x,a),V_h^{\star }(x)=\underset{a\in \mathcal{A}}{\max }{Q}_h^{\star }(x,a),V_{H+1}^{\star }(x)=0\end{array}$$

在分幕 MDP 设置下，Agent 目标是在和环境的交互过程中学得最优策略：对于每一个 $k\ge 1$，在第 $k$ 幕的开始，对手会对抗挑选一个初始状态 $s_1^k$，Agent 挑选出策略 ${\pi }^k$，使用该策略与环境交互直至幕结束。使用 $V_1^{\star }(x_1^k)-V_1^{{\pi }^k}(x_1^k)$ 衡量当前策略的遗憾，总计遗憾定义为

$$\mathrm{Regret}(K)=\sum _{k=1}^K\left[V_1^{\star }(x_1^k)-V_1^{{\pi }^k}(x_1^k)\right]$$

我们研究的核心是 Linear MDP，在这里 状态转移和奖励函数 被假设为 在某一个特征映射上是线性的，但是策略的形式并没有被假设为线性的。这样的假设可以推出一个关键性质，动作价值函数也是线性的。注意，这里的线性假设类似于统计建模中的数据生成机制的假设。

Assumption: Linear MDP：$\mathrm{MDP}(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$ 是线性的，当存在一个特征映射 $\varphi :\mathcal{S}\times \mathcal{A}\to {\mathbb{R}}^d$，使得对于每一个 $h\in [H]$，存在 $d$ 个定义在 $\mathcal{S}$ 上的未知的符号测度 ${\mu }_h=({\mu }_h^{(1)},\dots ,{\mu }_h^{(d)})$ 以及一个未知的向量 ${\theta }_h\in {\mathbb{R}}^d$，使得对于任意 $(x,a)\in \mathcal{S}\times \mathcal{A}$

$${\mathbb{P}}_h(\cdot \mid x,a)=⟨\varphi (x,a),{\mu }_h(\cdot )⟩,r_h(x,a)=⟨\varphi (x,a),{\theta }_h⟩$$

这里我们不失一般性地假设特征映射 $\varphi$ 被归一化了，即对于所有 $(x,a)$，$\Vert \varphi (x,a)\Vert \le 1$，并且对于所有 $h$，$\max \{\Vert {\mu }_h(\mathcal{S})\Vert ,\Vert {\theta }_h\Vert \}\le \sqrt{d}$。

虽然这里面假设了线性，但是转移核 ${\mathbb{P}}_h(\cdot \mid x,a)$ 仍然可能有无限的自由度，因为 ${\mu }_h$ 是一个未知的测度，而不是一个有限维的矩阵参数化的形式。熟悉的 Tabular MDP 就是一个 Linear MDP。Linear MDP 的最关键性质是其动作价值函数的线性性，因此在设计 RL 算法时只需要关注线性的 Q 函数就可以。

Property: Linearity of Action-value Function in Linear MDP：对于一个 Linear MDP 和其任意策略 $\pi$，存在未知的参数向量 $\{{\mathbf{w}}_h^{\pi }{\}}_{h=1}^H$，使得对于所有 $(x,a,h)\in \mathcal{S}\times \mathcal{A}\times [H]$，都有 $Q_h^{\pi }(x,a)=⟨\varphi (x,a),{\mathbf{w}}_h^{\pi }⟩$。