What is reinforcement learning

David Silver deep Reinforcement Algorithm learning + Project Presentation Zhou Bolei: Reinforcement Learning Platform online materials: David Silver open course on Reinforcement learning Chinese and practice

How do agents learn from their interactions with the environment by receiving feedback on success and failure, reward and punishment

There is a very important prerequisite, that is, when an agent interacts with the environment, it needs the environment to provide feedback information — Reinforcement information or Reward information at all times, so that the agent can know which behaviors can get positive rewards and which behaviors can get negative rewards, and adjust its behavior strategy accordingly.

This way of learning is very similar to how animals build conditioned responses based on reinforcement-they recognize pain and hunger as negative rewards, and pleasure and food as positive rewards, and act accordingly.

In the field of reinforcement learning, “reward” is the general name of positive reward and negative reward.

In other environments, rewards occur less frequently and may occur late.

For example, in board games such as Go, chess, TicTacToe, and so on, each time the reward always appears at the end of the board game. This problem is called delay reliability assignment problem and it is an important problem in reinforcement learning

Reinforcement learning is a branch of machine learning: supervised learning, unsupervised learning and reinforcement learning

Characteristics of reinforcement learning:

1. No monitoring data, just reward signals
2. The reward signal is not necessarily real-time, but it can be delayed, sometimes much later.
3. Time (sequence) is an important factor
4. Current behavior affects subsequent received data

Environmental agent interaction model

Some basic concepts in reinforcement learning

• Incentive Reward

  Rt R_t Rt is the feedback of the signal, it’s a scalar, it’s a reflection of how well the individual is doing at time T. The individual’s job is to maximize cumulative rewards.

  Reinforcement learning is based on the “reward hypothesis” : all problem-solving goals can be described as maximizing cumulative rewards.

• Sequential Decision Making

  • Goal: Select a set of behaviors to maximize overall future rewards
  • These behaviors can be a long-term sequence
  • Rewards can and usually are delayed
  • Sometimes it’s better to sacrifice immediate (short-term) rewards for more long-term rewards

• Agent & Environment

  Reinforcement learning problems can be described from both individual and environment.

  At time T, the individual can:

  1. There is an observation assessment of the environment Ot O_t Ot,
  2. I have an action At At At,
  3. Get a reward signal from the environment.

  The environment can:

  1. Receiving individual actions At A_t At,
  2. Update environmental information while allowing the individual to get the next observation,
  3. Give the individual a reward signal.

  

• History and status History & State

  • history

    History is A sequence of observations, actions, rewards: H t=O 1,R 1,A 1,.. O T − 1,R T − 1,A T − 1, O t,R t,A T H_t=O_1,R_1,A_1… ,O_{t-1},R_{t-1},A_{t-1},O_t,R_t,A_t Ht=O1,R1,A1,… Ot – 1, Rt – 1, the At – 1, Ot, Rt, ats

  • state

    A state is all the existing information that determines the future. It is a function of history: St= F (Ht) S_t= F (H_t) St= F (Ht)

  • Environment state

    Is a private rendering of the environment, including all the data the environment uses to determine the next observation/reward

    It is often not completely visible to the individual, that is, the individual sometimes does not know all the details of the state of the environment.

    Even when the state of the environment is completely visible to the individual, this information may contain irrelevant information.

  • The individual state

    Is the internal representation of the individual, including all the information that the individual can use to determine future actions.

    Individual state is the information that reinforcement learning algorithms can use, which can be a function of history: Sta= F (Ht) S^a_t= F (H_t) Sta= F (Ht)

  • State information

    Including all useful information in history, also known as Markov states.

• Markov Property of horse

  A state St S_t St is Markov if and only if: P [S T + 1 ∣ S t] = P [S t + 1 ∣ S 1, S t] [S_ P {t + 1} | S_t] = P [S_ (t + 1} | S_1,…, S_t] P = P [St + 1 ∣ St] [St ∣ S1 + 1,…, St]

  The next state is related to the current state, not the historical state

• Fully Observable environment

  Individuals can directly observe the state of the environment. In this case:

  Individual observation of the environment = individual state = environmental state

  Formally, this problem is a Markov Decision Process (MDP).

• Partially Observable Environments, Partially Observable Environments

  The individual indirectly observes the environment

  Eg: A poker player can only see their own cards and other cards that have been played, but not the state of the entire environment (including the opponent’s cards).

  In this case:

  Individual state ≠ environment state

  Formally, this problem is a partially observable markov decision process.

  The individual must construct its own representation of the state, for example: remember the complete history: Sta=Ht S^a_t = H_t Sta=Ht

  This approach is primitive and naive. There are other options, such as:

  1. Beliefs of environment state: Although the individual does not know what the environment state is, the individual can take advantage of the existing experience (data) and present the individual state at the current moment with the probability distribution of various individual known states:

  

  2. It has a Recurrent neural network: it feeds into the Recurrent neural network (RNN) to obtain a present individual state, without knowing the probability, based on the current individual state and individual observations at the current moment:

  

Reinforcement learning is the main component of the individual

Classification of reinforcement learning individuals

Individuals can have a combination of tools to solve reinforcement learning problems

• Solve the problem by establishing an estimate of the value of the state
• Solve the problem by directly establishing an estimate of the strategy.

These are tools in the toolbox that individuals can use. Therefore, individuals can be divided into the following three categories according to the classification of “tools” contained in them:

1. Value Based only on Value function:

   In such an individual, there is a value estimation function for the state, but there is no direct strategy function, which is indirectly obtained by the value function.

2. Policy Based only on Policy:

   In such an individual, the behavior is directly generated by the policy function, and the individual does not maintain an estimation function of the value of each state.

3. Actor- judge form Actor-Critic:

   The individual has both value function and strategy function. The two work together to solve the problem.

In addition, individuals can be divided into two categories according to whether they build a model of environmental dynamics when solving reinforcement learning problems:

1. Non-model-based individuals:

   Such individuals do not seek to understand how the environment works, but focus only on value and/or policy functions.

2. Model-based individuals:

   Individuals attempt to create a model that describes how the environment works to guide the updating of value or policy functions.

Learning & Planning

Exploration and Exploitation

Reinforcement learning is similar to trial-and-error learning in that individuals need to discover a good strategy from their interaction with the environment without losing too much reward in the process of trial and error. Exploration and utilization are two aspects that individuals need to balance when making decisions.

An analogy is that when you go to a restaurant,

“Explore” means you’re interested in trying new restaurants, probably going to a new restaurant that you haven’t been to before,

“Leverage” means you choose a favorite restaurant from a restaurant you’ve eaten at before, rather than trying a restaurant you’ve never been to before.

These two approaches are usually contradictory, but both are very important for solving reinforcement learning problems.

Prediction & Control

Markov decision making process

Markov decision process (MDP) describes completely observable environment, that is to say, the observed state content completely determines the characteristics required for decision making. Almost all reinforcement learning problems can be transformed into MDP

Markov Process

Markov Property

A certain state information contains all relevant history. As long as the current state is known, all historical information is no longer needed, and the current state can determine the future, this state is considered to have Markov property.

Markov properties can be described by the following state transition probability formula: P = P s s’ [‘ ∣ s t s t + 1 = s = s] P_ {} = ss ‘P [S_ (t + 1} = s’ | S_t = s] Pss’ = P [St + 1 = s’ ∣ St = s] under the state transition matrix defines all the state transition probability: P = (P 11… P 1 n ⋮ ⋱ ⋮ p 1 n… p n n ) P = \begin{pmatrix} p_{11} & \dots & p_{1n} \\ \vdots & \ddots &\vdots \\ p_{1n} & \dots & p_{nn} \end{pmatrix} P = ⎝ ⎜ ⎛ p11 ⋮ p1n… ⋱… P1n ⋮ PNN ⎠⎟⎞ where n is the number of states, the sum of elements in each row of the matrix is 1

Markov Process

Markov Reward Process

Markov reward process adds reward R and attenuation coefficient γ on the basis of Markov process:

.
,p,r,γ>

R is a reward function. S reward is under a certain time (t) is under a state of S (t + 1) in the next moment can obtain the reward expectation R S = E/R t + 1 ∣ S t = S] R_s = E (R_ (t + 1} | S_t = S] Rs = E/Rt + 1 ∣ St = S attenuation coefficient Discount Factor: γ∈ [0, 1]

The figure below shows an example of the “Markov reward process” graph, which adds rewards for each state on the basis of the “Markov process”. Since there is no calculation related to attenuation coefficient, this graph does not specify the value of attenuation coefficient.

Harvest Return

Value Function

A value function gives the long-term value of a state or behavior.

Definition: a markov reward in the process of the value of a state function is starting from the status of the expectations of the markov chain harvest: v (s) = E/G t ∣ s t = s v (s) = E [G_t | S_t = s] v (s) = E = s] [Gt ∣ St

Note: Value can describe only a state, a behavior in a state, and in some special cases, a behavior. Throughout the open Video course, except specifically, the convention uses the state value function or value function to describe the value against the state; Behavior value function is used to describe the value of performing a certain behavior in a certain state. Strictly speaking, behavior value function is the abbreviation of “state behavior pair” value function.

Illustrate harvest and value calculations

For the convenience of calculation, the sample graph of “Student Markov Reward Process” is expressed in the form of the following table.

The second row in the table corresponds to the instant reward value of each state, and the numbers in other areas are the state transition probability, which is the probability of changing from the state in the row to the state in the column:

Consider the following four Markov chains. It is calculated that when γ= 1/2, the harvest of state S1 S_1 S1 at t=1 (S1=C1 S_1 = C_1 S1=C1) is as follows:

It can also be understood from the above table that harvest is for a certain state in a Markov chain.

When gamma = 0, the value of the instant reward for each state is the same as that state.

When γ≠ 0, the value of each state needs to be calculated. Here, the value of each state under the condition that γ is 0, 0.9 and 1 respectively is given, as shown in the figure below.

The number inside each status circle indicates the value of the status, while R=-2 outside the circle indicates the immediate reward for the status.

Derivation of value function

Markov Decision Process

Compared with markov reward process, Markov decision process has one more action set A

It is A tuple like this:

. It looks very similar to the Markov reward process, but the P and R here correspond to the specific action A,
,>

Unlike markov reward processes that correspond only to one state, A represents A finite set of actions. The specific mathematical expression is as follows:

• Example — Student MDP

The following figure shows a possible MDP state transition diagram.

The red text in the figure represents the action taken, not the previous state name.

Strategy Policy

Value function based on strategy π

V π(s) v_{\ PI}(s) vπ(s) is defined as a state value function based on policy π under MDP.

Represents the expected gain from following the current policy starting at state S; Or measure the value of an individual in state S when executing the current strategy π. Mathematics said as follows: v PI PI (s) = E [G t ∣ s t = s] v_ (s) = {\ PI} E_ \ PI [G_t | S_t = s] v PI PI (s) = E = s] [Gt ∣ St

Note: Strategies are used to describe the probability of performing different behaviors in different states.

Q π(s,a) q_\ PI (s,a) qπ(s,a) behavior value function is defined to represent the expected harvest of a specific behavior a in the current state S under the implementation of strategy π.

Behavior value function is generally corresponding to a specific state, a more elaborate description is the state behavior versus value function. The formula of behavioral value function is described as follows: Q PI PI (s, a) = E/G t ∣ s t = s, a t = a] q_ \ PI (s, a) = E_ \ PI [G_t | S_t = s, A_t = a] q PI PI (s, a) = E [Gt ∣ St = s, the At = a]

Bellman Expectation Equation

The optimal

• Optimal value function

  Optimal state value function V∗(x) V_*(x) V∗(x) refers to the selection of the function that maximizes the value of state S among the state value functions generated from all strategies:

PI PI V V ∗ = m x V_ (s) * = \ underset {\ PI} {Max} V_ \ PI (s) V ∗ = PI maxv PI (s)

Similarly, optimal behavioral value function Q ∗(S,a) q_*(S,a) q∗(s,a) refers to the function with the greatest value to state behavior < S,a> < S,a> < S,a>,a> from the behavioral value function generated by all strategies: Q ∗ (s, a) = m a PI PI q x q_ (s, a) * (s, a) = \ underset {\ PI} {Max} q_ \ PI (s, a) q ∗ (s, a) = PI maxq PI (s, a)

• The optimal strategy

  Policy π is superior to policy π ‘when, for any state S, the value of following policy π is not less than that of following policy π’ :

  

  Theorem For any MDP, the following holds:

  • There is an optimal strategy that is better than or at least equal to any other strategy;
  • All optimal strategies have the same optimal value function;
  • All optimal strategies have the same behavior value function.

• Find the optimal strategy

  The optimal strategy can be found by maximizing the optimal behavior value function:

  

Bellman Optimality Equation

Dynamic programming seeks optimal strategies

Introduction;

Iterative strategy Evaluation for Iterative Policy Evaluation

The theory of

example

Check the world

Known:

State space S: as shown in figure. S1-s14 non-terminated state, ST terminated state, two positions as shown in the gray square below;

Behavior space A: {n, e, S, W} can have four behaviors of southeast, northwest movement for any non-terminating state;

** Transfer probability P: ** Any action attempting to leave the grid world will not change its position, the rest of the condition will be 100% transferred to the action pointing state;

** Instant reward R: ** Any transfer between non-terminated states will be rewarded with -1 instant reward, and entering terminated states will be rewarded with 0 instant reward;

Attenuation coefficient γ : 1;

Current strategy PI: * * * * Agent by random action strategy, in any one the termination conditions have equal chance to take any move the behavior, namely the PI (n | •) = PI (e | •) = PI (|, s) = PI | • (w) = a quarter.

** Problem: ** Evaluates a given strategy in this grid world.

This problem is equivalent to solving the value function of (state) in the grid world under a given strategy, that is, solving the value of each state in the grid world under a given strategy.

Iterative solution (iterative strategy evaluation)

State values converge after the 153rd iteration

• How to improve your strategy

Through the example of the grid world, we get a method of optimizing the strategy, which is divided into two steps:

First we iteratively update the value function under a given strategy:

Then, on the basis of the current strategy, the behavior is selected greedily, which increases the value of the subsequent state the most:

In the lattice world, the value iteration based on a given strategy eventually converges to the optimal strategy, but it is not a common phenomenon that the optimal strategy can be found through a round of iterative calculation of value combined with strategy improvement. Often, there is a need to continue to evaluate improvement strategies, many times over. However, this method always converges to the optimal strategy π∗ \ PI ^* π∗.

Policy Iteration

Value iteration

Value iteration is also derived based on Behrman optimal equation, but value iteration transforms Behrman optimal equation into Update rule to carry out continuous backtracking iteration, without the participation of policy in the whole iteration process

1. Iterating to find the optimal value function: first continuously iterating the Behrman optimal equation (i.e., maximizing the Q function) to get the optimal V *
2. Optimal policy extraction process: use Argmax to reconstruct the Q function, and then find that the maximum action is the policy he chooses

Compare Policy Iteration with Value Iteration