机器学习强化学习基础

理解心理学中的强化学习，我认为应该首先讲AI里面的强化学习

1. 强化学习基本概念的定义

我们生活的世界充满了各种交互，人类通过行动影响周围的环境，而环境又反馈给我们不同的结果或奖励。在强化学习中，环境类似于我们生活中的外部世界，它是Agent（智能体）与之交互的外部系统。在每一个时间步，环境会向Agent提供当前的状态（State），Agent基于此做出相应的动作（Action），环境则根据这些动作更新状态，并可能给予一定的奖励（Reward）。这种循环式的互动就像我们生活中的决策与反馈过程，推动着Agent不断学习和改进。

图1 智能体与环境的交互关系

因此，强化学习中通常用四元组 $(S,A,P,R)$ 来形式化定义一个环境（Env）。

$$Env=(S,A,P,R)$$

其中，每个元素的定义如下：

• S (States): 状态集合，表示环境中所有可能的状态。

• A (Actions): 动作集合，表示在每个状态下Agent可以执行的所有可能动作。

• P (Transition Probabilities): 状态转移概率函数，描述在执行某个动作后从一个状态转移到另一个状态的概率。通常表示为 $P(s'|s,a)$ 。

• R (Rewards): 奖励函数，描述在执行某个动作后从一个状态转移到另一个状态时得到的即时奖励。通常表示为 $R(s, a, s')$ 。

马尔可夫决策过程（Markov Decision Process, MDP）是一个数学模型，用于描述一个决策问题，在该问题中，决策者（Agent）在不同状态之间进行选择（行动），以最大化其长期回报。当我们说“环境是一个MDP”时，意思是我们可以用MDP的形式化描述来定义环境的动态行为。MDP为我们提供了一个结构化的方式来描述Agent与环境的交互，这包括状态、动作、状态转移和奖励。这种描述方式使我们能够利用动态规划和强化学习算法来求解最优策略，从而在给定环境中实现目标。

1. Frozen Lake

Frozen Lake 是一个经典的强化学习问题，AI相关专业中通常使用该问题解释和演示动态规划和强化学习中的基本概念。我们将通过这个例子介绍以下几个重要概念：Agent、State、Transmission Function 和 Reward。

1. Agent

在强化学习中，Agent 是指在环境中进行决策和行动的智能体。它观察环境状态，选择行动，并根据行动的结果更新其策略。

在 Frozen Lake 例子中，Agent 是一个在冰湖上移动的角色（例如，一个小人）。它的目标是从起点（Start）移动到目标（Goal）而不掉进冰窟窿（Hole）。

1. State

State（状态）是描述当前环境的情况或配置。在 Frozen Lake 中，状态$$(s)$$可以表示 Agent 在网格中的位置。

Frozen Lake 可以被表示为一个 8 × 8 的网格，包含以下几种状态：

• S: Start（起点）

• F: Frozen（冰面，可安全行走，图中白色部分）

• H: Hole（冰窟窿，掉进去就失败，图中蓝色部分）

• G: Goal（目标）

图2 冰湖游戏的状态

每个状态都是网格中的一个单元格，Agent 从一个单元格移动到另一个单元格。我们用如下代码构建环境中的状态空间：

class frozen_lake:
    n_row = 8
    n_col = 8
    
    def _init_(self, eps=.2, seed=1234):
        
        # get occupancy
        self.rng = np.random.RandomState(seed)
        self.layout = layout
        self.get_occupancy()
        # define MDP
        self._init_S()
        self._init_A()
        self._init_P()
        self._init_R()

    def _init_S(self):
        '''Define the state space
        '''
        # all possible state
        self.nS = frozen_lake.n_row*frozen_lake.n_col
        self.S  = list(range(self.nS))
        self.state = self.cell2state(self.curr_cell)
        # define the terminal states: goal, holes
        self.goal_state = self.cell2state(self.goal)
        self.hole_states = [self.cell2state(h) for h in self.hole_cells]
        self.s_termination = self.hole_states+[self.goal_state]

其中 $S$ 为状态集合，在代码中用env.S来表示， $A$ 为动作集合，在代码中用env.A来表示。

1. Action

Action（行动）是 Agent 可以在每个状态下执行的操作。在 Frozen Lake 中，Agent 有四种可能的行动：

• 上 (Up)

• 下 (Down)

• 左 (Left)

• 右 (Right)

这些行动会导致 Agent 从当前状态移动到相邻的状态（如果没有超出网格边界）。

    def _init_A(self,)
        '''Define the action space 
        '''
        self.directs = [
            np.array([-1, 0]), # up
            np.array([ 1, 0]), # down
            np.array([ 0,-1]), # left
            np.array([ 0, 1]), # right
        ]
        self.nA = len(self.directs)
        self.A  = list((range(self.nA)))

1. Transmission Function (P)

Transmission Function（状态转移函数）定义了在执行某个行动后，环境如何从一个状态转移到另一个状态，以及每个转移的概率。 在 Frozen Lake 中，状态转移函数可以表示为 $P(s' | s, a)$，即在状态 $s$ 执行动作 $a$ 后转移到状态 $s'$ 的概率。例如，Agent从 $(0,0)$ 点出发， $(0,0)$ 为当前的状态 $s$，在执行向下移动的动作后，到达 $(1,0)$，为新的状态 $s'$ 。

    def _init_P(self):
        '''Define the transition function, P(s'|s,a)

            P(s'|s,a) is a probability distribution that
            maps s and a to a distribution of s'. 
        '''

        def p_s_next(s, a):
            p_next = np.zeros([self.nS])
            cell = self.state2cell(s)
            # if the current state is terminal state
            # state in the current state 
            if s in self.s_termination:
                p_next[s] = 1 
            else:
                for j in self.A:
                    s_next = self.cell2state(
                        np.clip(cell + self.directs[j],
                        0, frozen_lake.n_row-1))
                    # the agent is walking on a surface of frozen ice, they cannot always
                    # successfully perform the intended action. For example, attempting to move "left"
                    # may result in the agent moving to the left with a probability of 1-ε.
                    # With probability ε, the agent will randomly move in one of the 
                    # other possible directions.
                    if j == a:
                        p_next[s_next] += 1-self.eps
                    else:
                        p_next[s_next] += self.eps / (self.nA-1)
                
            return p_next
        
        self.p_s_next = p_s_next

1. Reward

Reward（奖励）是 Agent 执行动作后从环境中获得的反馈。奖励用于指导 Agent 学习最佳策略，以实现其目标。 在 Frozen Lake 中，奖励机制通常如下：

• 到达目标状态（G）：+1 分

• 掉入冰窟窿（H）：-1 分

• 其余情况：0 分

    def _init_R(self):
        '''Define the reward function, R(s')

        return:
            r: reward
            done: if terminated 
        '''
        def R(s_next):
            if s_next == self.goal_state:
                return 1, True
            elif s_next in self.hole_states:
                return -1, True
            else:
                return 0, False
        self.r = R

1. 强化学习的目标

在强化学习中，目标是让智能体（Agent）学习一个策略（Policy），以最大化其在给定环境中的长期累积奖励。具体来说，智能体通过与环境交互，根据获得的奖励，不断调整其行为策略，使得在每一步行动中，智能体能够选择最优的行动来实现这一目标。

1. 策略（Policy）

策略 $\pi$ 是一个映射，定义了Agent在每个状态 $s$ 应该选择的动作 $a$。策略可以是确定的，即 $\pi(s)=a$，或者是随机的，即 $\pi(s|a)=P(s|a)$。

1. 预期累计奖励（Expected cumulative reward）

计算预期累计奖励是强化学习的核心目标之一，它涉及估计在给定策略下从当前状态开始的长期回报。 首先计算累计奖励。初始化状态 $s_1$，选择一个初始动作 $a_1$，随机获得奖励 $r_1$，同时进入新状态。重复步骤，在状态 $s_{t-1}$ 执行动作 $a_{t-1}$，观察到新的状态 $s_t$ 和即时奖励 $r_t$。根据当前策略在新状态 $s_t$ 选择下一个动作 $a_t$。以此类推，得到即时奖励 $r_{t+1}$，进入新状态 $s_{t+1}$。

由此得到，从初始状态开始得到累计奖励 $G_1=r_1+\gamma{r_2}+\gamma^2{r_3}+\gamma^3{r_4}+…$，其中 $\gamma$ 是折扣因子（discount factor），用于权衡未来奖励的重要性， $0\leq\gamma\leq1$。以此类推， $G_t=r_{t}+\gamma{r_{t+1}}+\gamma^2{r_{t+2}}+\gamma^3{r_{t+3}}+…$， $G_t$ 是从时间 t 开始的累计奖励。 价值函数 $V(s)$ 表示在状态 $s$ 下按照某策略 $\pi$ 选择动作是的预期累计奖励。它的定义是：

$$V^\pi(s)=\mathbb{E}[G_t|s_t=s] =\mathbb{E}[r_{t}+\gamma{r_{t+1}}+…|s_t=s]\tag{1}$$

在给定状态 $s_t=s$ 和策略 $\pi$ 的情况下，我们可以把期望分解为对所有可能动作 $a$ 的加权期望，权重是按照策略 $\pi$ 在状态 $s$ 下选择动作 $a$ 的概率 $\pi(a|s)$：

$$V^\pi(s)=\sum_a\pi(a|s)\mathbb{E}[r_{t}+\gamma{r_{t+1}}+…|s_t=s,a_t=a]\tag{2}$$

已知 $G_t=r_t+\gamma{G_{t+1}}$，因此 $\mathbb{E}[G_t|s_t=s,a_t=a]=\mathbb{E}[r_t+\gamma{G_{t+1}}|s_t=s,a_t=a]$。可以进一步分 $G_{t+1}$，得到：

$$V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r_t+\mathbb{E}[\gamma{r_{t+1}}+\gamma^2{r_{t+2}}+…|s_{t+1}=s']|s_t=s,a_t=a]\tag{3}$$

由于马尔可夫性质，未来的奖励只依赖于当前状态和动作，并与过去的状态和动作无关。由价值函数定义可得， $V^\pi(s')=\mathbb{E}[r_{t+1}+\gamma{r_{t+2}}+…|s_{t+1}=s']$，简化（3）可得：

$$V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r_t+\gamma{V^\pi(s')}|s_{t+1}=s']|s_t=s,a_t=a,s_{t+1}=s']\tag{4}$$

$$V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r_t+\gamma{V^\pi(s')}|s_{t+1}=s']]\tag{5}$$

因此得到，状态价值函数的贝尔曼方程（Bellman equation）：

$$V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r_t+\gamma{V^\pi(s')}]\tag{6}$$

Bellman Equation 是强化学习和动态规划中的核心方程，用于描述在给定策略下的价值函数的递归关系。使用 Bellman Equation，我们可以估计给定策略的每个任意状态的值。

1. 价值函数（Value Function）与状态-动作价值函数（State-Action Q value Function）

根据同上方法，可以推得状态-动作价值函数的Bellman Equation为：

$$Q^\pi(s,a)=\sum_{s'}p(s'|s,a)[r_t+\gamma{Q^\pi(s',a')}]\tag{7}$$

价值函数 $V(s)$ 是在状态 $s$ 下的预期累计奖励，用于评估状态的好坏，对于策略 $\pi$ 定义为：

$$V^\pi(s)=\sum_a\pi(a|s)\mathbb{E}[r_{t}+\gamma{r_{t+1}}+\gamma^2{r_{t+2}}…|s_t=s,a_t=a]$$

状态-动作价值函数 $Q(s,a)$ 是在状态 $s$ 执行动作 $a$ 后的预期累计奖励，对于策略 $\pi$ 定义为：

$$Q^\pi(s,a)=\mathbb{E}[r_{t}+\gamma{r_{t+1}}+\gamma^2{r_{t+2}}…|s_t=s,a_t=a]$$

由上可得，两者的关系是：

$$V^\pi(s)=\sum_a\pi(a|s)Q^\pi(s,a)$$

因此，强化学习的最终目标是找到一个最优策略最大化价值：

$$\pi^*=arg\max_\pi{V^\pi(s)}$$