Reinforcement Learning-Theory and Algorithms Notes [1] MDP

type

status

date

slug

summary

Markov Decision Process

Infinite-Horizon MDPs

: state space, finite/countably infinite : action space : transition function : reward function : discount factor. 定义了范围(horizon)。 : initial state distribution, 初态。

objective, policies, and values

在每一步 , agent 采取 , 得到瞬时reward , 并采样得到关于next state的observation . 此处我们有一条 trajectory .

广义而言，policy 是从 trajectory 到 action 的映射。Stationary policy 特指，即 action 只取决于 current state. 如果再加上deterministic, 那就是 .

给定策略和初态，我们定义 value function :

期望来源于状态转移和策略中的随机性。

同理, action-value (或 Q-value)定义为：

由于 , 两者都 bounded by .

agent的优化任务在于：find .

Bellman Consistency Equations for Stationary Policies

Lemma: 易得是的一阶展开

根据apply对象，令向量，，令矩阵，其中为概率

对于下的 state-action pair, 定义其 转移矩阵

因此对于 deterministic 的情况，有

则根据状态转移关系，引理的期望形式可化简为

Corollary:

Bellman Optimality

Theory: 存在 stationary and deterministic for all and ,

我们称其为最优策略。存在性：最大未来收益与无关。即：

根据马尔可夫性易证。运用上式可以得到：

其中步骤的依据是定义最优策略:

它是deterministic和stationary的。递归调用得到：

得证。 Theory: 符合Bellman optimality的满足:

是最优策略。

Finite-Horizon MDPs

where is the time step (因此多数时候假设time-dependent). 假设的上界为则：

其余定义类比 infinite-horizon.