Q-表格是一种简单的策略迭代算法，用于解决MDP问题。它通过构建一个Q-表来估计在给定状态下采取某个动作的价值。Q-表中的每个元素 Q(s, a) 代表了在状态s下采取动作a之后预期的长期回报。

Q-学习算法步骤：

1、初始化：创建一个Q-表，其中包含所有可能的状态-动作对，并将它们的初始值设为0或随机小数值。
2、选择动作：基于当前状态s，选择一个动作a。这一步可以使用ε-greedy策略，即以一定概率ε随机选取动作，以(1-ε)的概率选取当前已知的最佳动作。
3、执行动作并观察：根据选定的动作a，让智能体与环境交互，得到新的状态s'和即时奖励r。
4、更新Q-表：根据观测到的结果更新Q-表。更新规则通常是：

image.png

5、重复：重复步骤2至4直到达到终止条件，如达到最大迭代次数或找到满意的解决方案。

举个例子：

构建一个简单的迷宫游戏环境，在这个环境中，智能体需要找到从起点到终点的路径。为了简化问题，我们假设迷宫是一个4x4的网格，其中有一些障碍物。

环境设定如下
状态：每个格子代表一个状态。
动作：上、下、左、右四个方向移动。
奖励：到达终点时获得+100分；碰到墙壁或障碍物时获得-10分；其他情况下为-1分。
终止条件：到达终点或达到最大步数。
获取Q-表格

import numpy as np
import random

# 迷宫布局
maze = [
    [0, 0, 0, 0],
    [0, -1, 0, -1],
    [0, 0, 0, 0],
    [-1, 0, 0, 1]
]

# 动作集
actions = ['up', 'down', 'left', 'right']

# 初始化Q表
q_table = np.zeros((len(maze), len(maze[0]), len(actions)))
q_table
# 参数设置
alpha = 0.1  # 学习率
gamma = 0.9  # 折扣因子
epsilon = 0.5  # 探索与利用的平衡
num_episodes = 1000  # 训练轮次
max_steps = 100  # 每轮的最大步数

# 获取下一个位置
def get_next_position(position, action):
    if action == 'up':
        return (position[0] - 1, position[1])
    elif action == 'down':
        return (position[0] + 1, position[1])
    elif action == 'left':
        return (position[0], position[1] - 1)
    elif action == 'right':
        return (position[0], position[1] + 1)
    
# 检查是否越界
def is_valid_position(position):
    x, y = position
    return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != -1

# Q-学习算法
for episode in range(num_episodes):
    state = (0, 0)  # 起点
    for step in range(max_steps):
        # 选择动作
        if random.uniform(0, 1) < epsilon:
            action_index = random.randint(0, len(actions) - 1)
        else:
            action_index = np.argmax(q_table[state[0], state[1], :])
        

        action = actions[action_index]
        print('action:',action)
        next_state = get_next_position(state, action)
        print('next_state:',next_state)
        
        # 如果下一个位置无效，则保持原地不动
        if not is_valid_position(next_state):
            next_state = state
        print('下一个位置是否有效：',is_valid_position(next_state))
        
        # 计算奖励
        reward = maze[next_state[0]][next_state[1]]
        print('奖励：', reward)

        # 更新Q表
        old_value = q_table[state[0], state[1], action_index]
        next_max = np.max(q_table[next_state[0], next_state[1], :])
        
        new_value = (1 - alpha) * old_value + alpha * (reward + gamma * next_max)
        q_table[state[0], state[1], action_index] = new_value

        # 更新状态
        state = next_state

        # 如果到达终点则结束本轮
        if reward == 1:
            break

基于上述代码，迭代后的Q-表格如下：

image.png

Q-表格中的每个条目 Q(s, a) 表示在状态 s 下采取动作 a 后的预期长期回报。Q-表格中共16*4个元素，每个元素代表，在该位置上分别采取4个动作后的价值。比如，第一行[0.83490833 0.92766808 0.83490833 0.92767592]表示，在位置（或状态）上，分别采取上下左右四个动作后的价值。可以看出，向下和向右的价值差距不大，总得来说向右的价值是最大的，也有随机的因素。

image.png

如何使用Q-表格进行决策

我们已经训练了一个Q-表格，并希望使用它来指导智能体找到从起点到终点的最佳路径。
Q-表格使用

# 使用Q-表格选择动作并执行
state = (0, 0)  # 起点
path = [state]  # 记录路径

for step in range(max_steps):
    # 选择当前状态下Q值最高的动作
    action_index = np.argmax(q_table[state[0], state[1], :])
    action = actions[action_index]
    
    next_state = get_next_position(state, action)
    
    # 如果下一个位置无效，则保持原地不动
    if not is_valid_position(next_state):
        next_state = state
    
    # 更新状态
    state = next_state
    path.append(state)
    
    # 如果到达终点则结束
    if maze[state[0]][state[1]] == 1:
        print("Found the goal!")
        break

# 打印最终路径
print("Path taken:", path)

根据上述代码运行后的结果为：

image.png

这就是根据迷宫布局，智能体根据Q-表格得出的最佳路径。将其可视化后如下：

image.png

再将其与Q-表格对比，可以看出，智能体就是根据在当前位置上，采取动作后的Q价值最大进行路径选择的。

image.png