【Hierarchical RL】半马尔可夫决策过程 (SMDP) --＞分层强化学习

半马尔可夫决策过程，Semi-Markov Decision Processes (SMDP) 是一种用于分层强化学习的模型，适用于那些包含不规则时间步或长期延迟决策的任务。相比于标准的马尔可夫决策过程（Markov Decision Process, MDP），SMDP 能够处理不同时间间隔之间的决策问题，因此在强化学习中广泛应用于分层结构，尤其是需要长时间跨度或多步策略的复杂任务中。

不去幼儿园

2322人浏览 · 2024-10-13 11:45:00

不去幼儿园 · 2024-10-13 11:45:00 发布

📢本篇文章是博主强化学习（RL）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：

【强化学习】（30）---《半马尔可夫决策过程 (SMDP) -->分层强化学习》

半马尔可夫决策过程 (SMDP) -->分层强化学习

(3) Q-learning 在 SMDP 中的扩展

4. SMDP的分层架构

5. SMDP的学习流程

[Python] Q-learning实现

半马尔可夫决策过程，Semi-Markov Decision Processes (SMDP) 是一种用于分层强化学习的模型，适用于那些包含不规则时间步或长期延迟决策的任务。相比于标准的马尔可夫决策过程（Markov Decision Process, MDP），SMDP 能够处理不同时间间隔之间的决策问题，因此在强化学习中广泛应用于分层结构，尤其是需要长时间跨度或多步策略的复杂任务中。

上图展示了MDP的状态轨迹由小的、离散时间的转变组成，而smdp的状态轨迹由大的、连续时间的转变组成。

1. SMDP的核心思想

SMDP 通过扩展 MDP，使其能够处理可变时间步长的决策问题。在 SMDP 中，每个动作的执行时间不是固定的，而是可能持续多步。这在分层强化学习中非常重要，因为高层策略通常制定长期目标，低层策略则负责在多个时间步内执行具体的动作。

SMDP 的分层结构常用于分解复杂任务：

高层策略（High-Level Policy）：负责选择目标或子任务，这些目标需要较长时间来完成。
低层策略（Low-Level Policy）：在执行高层任务的过程中，低层策略在较短的时间步内选择具体动作。

2. SMDP的状态、动作和转移模型

在 SMDP 中，状态、动作和转移与标准 MDP 相似，但有所扩展：

状态（State, $(s)$ ）：描述环境的当前状态。
动作（Action, $(a)$ ）：可以是原始动作或子任务的选择。在分层结构中，低层策略根据高层策略设定的子目标选择具体动作。
时间间隔（Time Interval, $(\tau)$ ）：表示一个动作持续的时间，即从当前状态转移到下一个状态所需的时间步数。
转移概率（Transition Probability, $(P(s', \tau | s, a))$ ）：给定当前状态 $(s)$ 和动作 $(a)$ ，转移到下一状态 $(s')$ 并经历时间间隔 $(\tau)$ 的概率。

3. SMDP的关键公式

(1) 半马尔可夫决策过程的期望回报

SMDP 的目标是在一个可能存在不同时间间隔的任务中，最大化长期期望回报。其回报函数包括了时间间隔的折扣，因此目标是找到最优策略来最大化累积奖励。

假设 $(r_t)$ 是时间步 $(t)$ 的即时奖励， $(\gamma)$ 是折扣因子， $(\tau)$ 是动作持续的时间间隔。则总回报为：

$[ R = \sum_{t=0}^{\infty} \gamma^{\tau_t} r_t ]$

与标准 MDP 不同的是，SMDP 需要考虑动作执行的时间间隔对总回报的影响。

(2) Bellman方程

SMDP 的值函数可以通过 Bellman 方程扩展为半马尔可夫形式。在给定策略 $(\pi)$ 下，状态 $(s)$ 的值函数表示为：

$[ V^\pi(s) = \mathbb{E}_\pi \left[ r(s, a) + \gamma^\tau V^\pi(s') \right] ]$

其中：

$(V^\pi(s))$ 是状态 $(s)$ 的值函数。
$(r(s, a))$ 是在状态 $(s)$ 执行动作 $(a)$ 的即时奖励。
$(\gamma^\tau)$ 是折扣因子， $(\tau)$ 是动作持续时间。
$(s')$ 是转移后的状态。

(3) Q-learning 在 SMDP 中的扩展

SMDP 中的 Q-learning 算法类似于标准的 Q-learning，但需要考虑时间间隔的影响。其 Q 值更新公式为：

$[ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma^\tau \max_{a'} Q(s', a') - Q(s, a) \right) ]$

其中：

$(Q(s, a))$ 是状态 $(s)$ 下执行动作 $(a)$ 的 Q 值。
$(\alpha)$ 是学习率。
$(\tau)$ 是动作 $(a)$ 执行的时间间隔。

4. SMDP的分层架构

SMDP 在分层强化学习中通常用于建模高层策略和低层策略的不同时间尺度。这种架构使得算法能够应对长时间跨度的任务。

(1) 高层策略

高层策略在长时间间隔上操作，选择子目标或子任务。
每个高层策略选择的目标都可能需要多个时间步来实现，因此高层策略通过 SMDP 模型选择长期目标。

(2) 低层策略

低层策略执行具体的动作，通常每个时间步都进行更新。它通过高层策略设定的目标进行指导，执行实现该目标的具体动作。
低层策略通过标准强化学习算法（如 Q-learning 或 Actor-Critic）进行更新，但在分层结构下，它的目标由高层策略设定。

5. SMDP的学习流程

SMDP 的学习过程可以总结为以下步骤：

高层策略选择目标：高层策略根据当前状态，选择一个子目标 (g_t)，该子目标通常需要多个时间步来实现。
低层策略执行动作：低层策略根据高层策略设定的子目标，执行具体的动作 (a_t)，并尝试实现目标。
时间间隔的处理：当一个动作执行需要多个时间步时，SMDP通过时间间隔 (\tau) 来调整 Q 值和回报的计算，确保考虑到不规则的时间跨度。
Q-learning 更新：SMDP 中的 Q-learning 更新考虑了时间间隔对回报的影响，因此学习过程中，高层和低层策略都可以根据不同的时间尺度进行更新。

[Python] Q-learning实现

下面是Semi-Markov Decision Process (SMDP) 的 Python 伪代码。此伪代码展示了如何使用 SMDP 进行强化学习，尤其是使用 Q-learning 方法更新 Q 值。此伪代码假设任务中每个动作执行时间 $( \tau )$ 是可变的，并且使用时间间隔调整折扣因子 $( \gamma^\tau )$ 。

"""《SMDP伪代码》
    时间：2024.10.15
    作者：不去幼儿园
"""
import numpy as np

# 定义环境类（伪代码）
class Environment:
    def __init__(self):
        pass
    
    def get_state(self):
        # 返回当前状态
        pass

    def take_action(self, action):
        # 执行动作，返回奖励、下一个状态和动作执行所花费的时间
        next_state = None
        reward = None
        tau = None  # 时间间隔
        return next_state, reward, tau

# 定义SMDP的Q-learning算法
class SMDPAgent:
    def __init__(self, state_space_size, action_space_size, alpha=0.1, gamma=0.99, epsilon=0.1):
        # 初始化参数
        self.q_table = np.zeros((state_space_size, action_space_size))  # 初始化Q表
        self.alpha = alpha  # 学习率
        self.gamma = gamma  # 折扣因子
        self.epsilon = epsilon  # 探索率
        self.action_space_size = action_space_size
    
    def choose_action(self, state):
        # 根据epsilon-greedy策略选择动作
        if np.random.uniform(0, 1) < self.epsilon:
            return np.random.randint(0, self.action_space_size)  # 随机探索
        else:
            return np.argmax(self.q_table[state])  # 选择Q值最大的动作
    
    def update_q_value(self, state, action, reward, next_state, tau):
        # 使用Q-learning公式更新Q值，考虑时间间隔tau
        best_next_action = np.argmax(self.q_table[next_state])
        q_target = reward + (self.gamma ** tau) * self.q_table[next_state, best_next_action]
        self.q_table[state, action] += self.alpha * (q_target - self.q_table[state, action])

# 主函数（伪代码）
def main():
    # 初始化环境和SMDP代理
    env = Environment()
    agent = SMDPAgent(state_space_size=100, action_space_size=4)
    
    # 开始训练
    num_episodes = 1000
    for episode in range(num_episodes):
        state = env.get_state()  # 获取初始状态
        done = False
        
        while not done:
            action = agent.choose_action(state)  # 选择动作
            next_state, reward, tau = env.take_action(action)  # 执行动作
            
            # 更新Q值
            agent.update_q_value(state, action, reward, next_state, tau)
            
            state = next_state  # 转移到下一个状态

if __name__ == "__main__":
    main()

[Notice] 关键点：

choose_action 方法：基于 epsilon-greedy 策略选择动作，以平衡探索和利用。
update_q_value 方法：使用 SMDP 版本的 Q-learning 更新 Q 值，考虑时间间隔 $( \tau )$ 对折扣因子的影响，即 $( \gamma^\tau )$
时间间隔处理：方法中返回的时间间隔 $( \tau )$ ，用于更新 Q-learning 公式中的折扣因子。

该伪代码是强化学习中的 SMDP Q-learning 算法的基本实现，可用于需要不同时间跨度的任务中，如机器人控制、规划任务等。

由于博文主要为了介绍相关算法的原理和应用的方法，缺乏对于实际效果的关注，算法可能在上述环境中的效果不佳，一是算法不适配上述环境，二是算法未调参和优化，三是等等。上述代码用于了解和学习算法足够了，但若是想直接将上面代码应用于实际项目中，还需要进行修改。

6. SMDP的优点与挑战

(1) 优点：

处理长时间跨度任务：SMDP 能够自然处理包含不规则时间间隔的任务，因此适合在分层强化学习中用于高层策略选择。
时间尺度的灵活性：SMDP 支持动作的不同时间跨度，使其适合在多步操作的任务中进行优化。

(2) 挑战：

时间间隔的设计与调试：选择合适的时间间隔 $(\tau)$ 是一个关键问题，尤其在复杂任务中，如何平衡不同时间尺度的奖励和更新过程是一个难题。
数据效率：由于每个动作可能会持续多个时间步，更新频率相对减少，可能导致数据效率较低。

7. SMDP的应用场景

SMDP 适用于以下场景：

机器人控制：复杂任务如机械臂操作和移动机器人导航，通常需要多个时间步来完成一个子任务，SMDP可以很好地建模这些操作。
长时间跨度的规划任务：如多步骤规划任务、策略决策等，SMDP可以通过高层次的任务分解来应对长时间决策依赖。
时间不规则的任务：在一些任务中，动作的时间跨度是变化的，例如游戏中的策略选择、资源管理等，SMDP能够更灵活地处理这些任务。

8.总结

Semi-Markov Decision Processes (SMDP) 并不是某一篇具体的论文中首次提出的单一算法，而是对标准马尔可夫决策过程（MDP）的一种扩展，最早由 J.A. Bather 提出，并被应用到多个领域。SMDP 被广泛应用于强化学习中的分层结构，以处理可变的时间间隔问题。

不过，在强化学习领域中，Richard S. Sutton 和他的合作者们将 SMDP 引入强化学习中的工作可以作为一个重要的参考点。特别是在强化学习领域，Sutton 等人在其经典著作中讨论了 SMDP 的应用与算法。

可参考文献：

Sutton, Richard S., Precup, Doina, and Singh, Satinder. "Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning." Artificial intelligence 112.1-2 (1999): 181-211.

这篇论文详细描述了如何将时间抽象引入强化学习，并通过SMDP框架实现层次化的任务规划。