模型
设 是状态集,, 是终止状态集。对非终止状态 ,给定非空有限动作集 、转移 与代价 。
从状态 出发的动作序列是有限序列 ,满足 ,其中 、。对应的状态序列为 ;若 ,称 终止。假设从每个可达状态出发的极大动作序列都在有限步内终止。
状态值 满足
其中 对 。贪心策略由局部键 给出:
不必等于真实代价。上述 方程是 动态规划 在每条转移只有一个后继、聚合取 时的特例。
安全选择
若从 可达的每个非终止状态 都满足
则沿 的路径最优;对剩余步数归纳即可。安全选择通常由交换论证证明。拟阵 只是选择型的一类交换结构,不是本模型的公理。