Q-Learning算法

理论

Q-Learning是一种强化学习算法，用于学习在给定状态下采取不同行动的最佳策略。其公式如下：

\(Q(s,a) \leftarrow (1 - \alpha) \cdot Q(s,a) + \alpha \cdot (r + \gamma \cdot \max_{a'} Q(s',a'))\)

其中，\(Q(s,a)\)是在状态\(s\)下采取行动\(a\)的预期回报，\(\alpha\)是学习率，\(r\)是在状态\(s\)下采取行动\(a\)的即时回报，\(\gamma\)是折扣因子，\(s'\)是采取行动\(a\)后得到的新状态。\(\max_{a'} Q(s',a')\)是在新状态\(s'\)下采取不同行动所能获得的最大预期回报。

Q-Learning公式的意义是，在当前状态\(s\)下采取行动\(a\)，更新当前状态下采取行动\(a\)的预期回报\(Q(s,a)\)。更新公式中的第一项表示当前状态下采取行动\(a\)的原始预期回报，第二项表示从当前状态采取行动\(a\)后得到的新状态\(s'\)的最大预期回报。通过不断更新\(Q(s,a)\)，我们可以学习到在不同状态下采取不同行动的最佳策略。

将理论转换为简单易懂的python的代码：

alpha = 0.1
gamma = 0.5

# s 当前状态 就是一个位置信息
# a 执行动作 上下左右
# newS 当前状态执行动作后的新状态
# r 为执行动作a后，环境给的奖励
def updateQ(s, a, r):
    newS = None
    if a == 0: # 上
        newS = (s[0]-1, s[1])
    elif a == 1: # 下
        newS = (s[0]+1, s[1])
    elif a == 2: # 左
        newS = (s[0], s[1]-1)
    elif a == 3: # 右
        newS = (s[0], s[1]+1)

    Q[s][a] += alpha * (r + gamma * max(Q[newS]) - Q[s][a])

中间小插曲

刚开始看到理论后，就开始撸代码了，没有看其他人的写的代码， 结果翻车了。
根据我的理解，我刚开始代码的Q表是每个状态的价值表。动作的变化，引发环境改变，环境改变给出一个奖励， 然后在更新Q表。
大家一定要注意是对Q表存的是每个状态的每个动作的评价值
不过经过翻车，也算是加深了对Qlearning的理解

实际能运行demo

#coding:utf8
import random
import math
import gym
from gym import spaces
import numpy as np
S = "S" # 起始块
G = "G" # 目标块
F = "F" # 冻结块
H = "H" # 危险块
# 这个环境规则就是， 从S点走到G点，中间走到H点就GameOver
class MyEnv(gym.Env):
    metadata = {'render.modes': ['human']}

    def __init__(self):
        self.board = np.array([
            [S, F, F, F],
            [F, H, F, H],
            [F, F, F, H],
            [H, F, F, G],
        ])
        self.height, self.width = self.board.shape

        # 定义动作空间和观察空间
        self.action_space = spaces.Discrete(4) # 上下左右
        self.observation_space = spaces.Tuple((
            spaces.Discrete(self.height),
            spaces.Discrete(self.width)
        ))
        self.reset()

    def step(self, action):
        if action == 0: # 上
            next_pos = (self.current_pos[0]-1, self.current_pos[1])
        elif action == 1: # 下
            next_pos = (self.current_pos[0]+1, self.current_pos[1])
        elif action == 2: # 左
            next_pos = (self.current_pos[0], self.current_pos[1]-1)
        elif action == 3: # 右
            next_pos = (self.current_pos[0], self.current_pos[1]+1)

        assert self._is_valid_pos(next_pos)

        # 步骤越多模型越差
        self.steps += 0.1
        if self.board[next_pos] == H:
            reward = -self.steps -self.width*self.height
            self.done = True
        elif self.board[next_pos] == G:
            reward = -self.steps
            self.done = True
        else:
            reward = -self.steps - abs(next_pos[0]-3) - abs(next_pos[1]-3)
            self.done = False

        self.current_pos = next_pos
        return self.current_pos, reward, self.done, self.board[next_pos] == H

    def reset(self):
        self.current_pos = (0, 0)
        self.done = False
        self.steps = 0
        return self.current_pos

    def render(self, mode='human'):
        for i in range(self.height):
            for j in range(self.width):
                if (i, j) == self.current_pos:
                    print("*", end="")
                else:
                    print(self.board[i][j], end="")
            print()
        print()

    def _is_valid_pos(self, pos):
        if pos[0] < 0 or pos[0] >= self.height or pos[1] < 0 or pos[1] >= self.width:
            return False
        return True
    
def softmax(x):
    exp_x = np.exp(x)
    return exp_x / np.sum(exp_x)
    
# 定义获取当前位置动作的函数
def get_actions(row, col):
    actions = []
    if row < 3:  # 如果不在最后一行，则可以向下移动
        actions.append(1)
    if col < 3:  # 如果不在最后一列，则可以向右移动
        actions.append(3)
    if row > 0:  # 如果不在第一行，则可以向上移动
        actions.append(0)
    if col > 0:  # 如果不在第一列，则可以向左移动
        actions.append(2)
    return actions

env = MyEnv()
ACTIONS = np.arange(4)
ACTIONS_STR = '上|下|左|右'.split('|')

Q = np.random.rand(4, 4, 4)
for i in range(4):
    for j in range(4):
        actions = get_actions(i, j)
        for k in range(4):
            if k not in actions:
                # 经过soeftmax之后，执行这个动作的概率为0
                Q[(i, j, k)] = -float("inf")
            else:
                Q[(i, j, k)] = 0

def printQ():
    for i in range(4):
        for j in range(4):
            print("{}_{}: ".format(i,j), Q[(i,j)])

def getAction(s):
    action = np.argmax(softmax(Q[s]))
    return action

def train():
    alpha = 0.1
    gamma = 0.95
    # 90%概率
    useQ = 0.9
    for i in range(100):
        s = env.reset()
        while True:
            env.render()
            # 根据状态获取s, 选择一个动作
            can_actions = get_actions(s[0], s[1])
            action = getAction(s) if np.random.uniform() < useQ else np.random.choice(can_actions)
            assert action in can_actions
            nextPos, reward, done, isH =  env.step(action)
            if done: # game over 没有下一个状态
                Q[s][action] +=  alpha * (reward - Q[s][action])
                break
            else:
                Q[s][action] +=  alpha * (reward + gamma * max(Q[nextPos]) - Q[s][action])
            s = nextPos
def play():
    s = env.reset()
    env.render()
    while True:
        # 根据状态获取s, 选择一个动作
        action = getAction(s)
        print('执行了动作:', ACTIONS_STR[action])
        nextPos, reward, done, _ =  env.step(action)
        s = nextPos
        env.render()
        if done:
            print(reward)
            break

train()
printQ()
play()

展望

写这个花费了很久，第一个原因是Q表创建错误， 第二个是中间非常容易死循环。
写这个需要考虑到底需要迭代多少次合适，以及奖励应该怎么定合适，一定要有概率不按Q表选择动作， 因为容易出现死循环。训练步骤不能太少，Q表信息不够，也是容易出现死循环。
这个例子环境是固定的，环境变化，必须重新训练
奖励函数现在是 -step - 曼哈顿距离， 也就是说步骤越少以及距离越小，函数值越大
对无效动作给了-float("inf")， 充当动作的MASK， 使用softmax去映射，会得到0