强化学习及Q-Learning算法的简单理解

首先明确学习的概念，学习是系统为了适应环境而做出的长久的变化，以便在未来更有效率的处理类似的问题。
强化学习就是通过算法和训练，让程序的产生相应的变化，未来更好地处理类似问题。
Q-Learning就是其中一种简单的系统实现，通过Q-Table的不断更新，来产生长久的变化。

强化学习主要分为两部分：

1. 学习系统本身(即学习程序)
2. 环境(即学习程序要解决的问题所处的环境)

强化学习的流程：

1. 系统判定当前状态，根据策略采取行动
2. 系统获得环境的反馈
3. 系统根据反馈，更新策略
4. 重复上述步骤，直到问题解决

强化学习的特点：

1. 强化学习是一种无监督学习
2. 在状态S下，不同的行动A会有不同的反馈R
3. 反馈R的获得，通常是有延时的
4. 当前行动A，会对系统后续的行为产生影响

在强化学习中，通常用Q(S, A)来表示状态S下，采取动作A所带来的价值，所以这个算法就用Q-Learning作了它的名字。

Q-Learning核心思想：

关键点：状态、策略、行动、反馈

1. 通过Q-Table来记录每个状态S可以采用的行动A，Q-Table是一个二维矩阵，每一行代表一个状态，每一列代表一个行动，Q(S,A)的值表示在状态S下，采取行动A的权重(或者说成是能取得的收益)。
2. 特定的策略，在状态S下，通过Q-Table和策略，决定行动A；通常使用的策略是，在状态S下，找到Q(S, A)值最大的那一个A作为当前行动，为避免初始状态下的局部最优情况，通常还会引入随机性。
3. 反馈的获得，可以通过「反馈表」或者是「反馈算法」来获得环境对行动A的反馈R(S, A)。R(S, A)表示在状态S下，采取行动A，获得的反馈。
4. 策略更新，通过贝尔曼方程进行计算，更新Q-Table

核心概念：

• 状态-State，用S表示
• 行动-Action，用A表示
• 反馈-Reward，用R表示

stairs.png

以上图为例：

机器人娃娃的目标是到达楼梯顶部T

• 当前状态(即S)为3，
• 可采取的行动(即A)有"上"和"下"两种，
• 只有到达楼梯顶部时，我们给它的反馈(即R)为1，其他动作的即时反馈都为0(这个就是我们的反馈策略)
• 机器人娃娃不停的探索，直到它走到了T；每走一步，都会更新Q-Table；
• 走到T的这个动作所获得的奖励(Reward)，会在后面的训练过程中，逐渐传递到前面的每一个State(需要加入随机，不然会出现局部最优问题)。就像是你从台阶5走到台阶6的时候，会得到现金，那么你就会总想到达台阶5，以此类推。

我们可以像下面一样，构造一个Q-Table

状态	下	上
台阶1	0	0
台阶2	0	0
台阶3	0	0
台阶4	0	0
台阶5	0	0

初始值都为0，是因为开始的时候，每一步的价值对我们都是一样的
类似的，我们可以构造一个R-Table，用来查看我们每一个行动带来的价值，即反馈R

状态	下	上
台阶1	-1	0
台阶2	0	0
台阶3	0	0
台阶4	0	0
台阶5	0	1

R-Table中，R(台阶1，下)的值为-1，表示这个动作不可执行
R(台阶5， 上)的值为1，因为这个动作让我们到达了目标
根据上面的两个表，我们不停的采取行动，然后根据获得的反馈更新Q-Table，直到我们可以得到一个训练好的Q-Table，通过这个Q-Table，机器人娃娃就能以最效率的方式到达目的地。

Q-Table更新公式：

参数说明：

1. α是学习速率，在[0,1]区间取值，表示反馈对当前策略的影响程度。0表示完全不考虑反馈，1表示只看反馈，不看历史经验。

2. r表示R(S, A)，通过「反馈表」或者「反馈算法」获得的反馈值

3. ：S′是状态S时采取行动A之后到达的状态；表示在S′状态时，能获得的最大Q值，即历史经验，或者说是记忆中的利益

4. γ表示折扣因子，代表历史经验中未来利益的重要性，如果为0，表示只看眼前利益r

实现步骤：

1. 初始化Q-Table
2. 定义Reward获取方法
3. 制定策略，即在状态S下，如何通过Q-Table选取行动A
4. 初始化状态S，可以固定，也可以随机
5. 根据当前状态S，采取行动A，并获得反馈R
6. 使用更新公式，对Q-Table进行更新
7. 重复步骤5，6，直到命中退出条件(比如成功、失败、走出了迷宫、到达了目的地等等)
8. 重复4-7流程N次，N代表训练的回合数

Demo：
"-----T"

比如上面的一个字符串，机器人从任意一点进入字符串，可以向左或者向右走一步，最终的目标是走到字母T的位置。

我们的code进行20次训练，得到更新后Q-Table，这时机器人再进入字符串，就能以最效率的方式，走到字母T

import numpy as np
import random

ALPHA = 0.1
GAMMA = 0.9
EPSILON = 0.9
EPOCH = 20
N_STATE = 6
ACTIONS = ["left", "right"]

np.random.seed(2)

Q_Table = np.zeros((N_STATE, len(ACTIONS)))


def get_reward(S, A):
    if S == 5:
        R = 1
    elif S == 4 and A == 'right':  # S!=5
        R = 1
    else:
        R = 0
    return R


def take_action(S):
    if S == 0:
        return 1, 'right', np.max(Q_Table[1, :])
    maxQ = np.max(Q_Table[S, :])
    if maxQ == 0 or np.random.uniform() > EPSILON:
        if maxQ == 0:
            print("maxQ is 0")
        else:
            print("Random 0.1 hit")
        action = np.random.choice(ACTIONS)
    else:
        idx = np.argmax(Q_Table[S, :])
        print("IDX:", idx)
        action = ACTIONS[idx]
    if action == 'left':
        SN = S - 1
    else:
        SN = S + 1
    maxQ = np.max(Q_Table[SN, :])
    return SN, action, maxQ


def get_value(S, A):
    if A == 'left':
        return Q_Table[S, 0]
    else:
        return Q_Table[S, 1]


def set_value(S, A, V):
    if A == 'left':
        Q_Table[S, 0] = V
    else:
        Q_Table[S, 1] = V


def update_q(S, A, MQ):
    value = (1 - ALPHA) * get_value(S, A) + ALPHA * (get_reward(S, A) + GAMMA * MQ)
    set_value(S, A, value)


for loop in range(EPOCH):
    print("Loop:", loop)
    S = 0
    step = 0
    steps = []
    while S != 5:
        SN, action, maxQ = take_action(S)
        update_q(S, action, maxQ)
        S = SN
        step += 1
        steps.append(action)
    print("State:", S, "TotalSteps:", step, "\nDetail:", steps)

print("Q_Table:", Q_Table)

S = random.randint(0, 5)
print("Initial S", S)
step = 0
steps = []
while S != 5:
    SN, action, maxQ = take_action(S)
    S = SN
    step += 1
    steps.append(action)
print("Real State:", S, "TotalSteps:", step, "\nDetail:", steps)