Chapter 1 Basic Concepts of Reinforcement Learning

Reinforcement Learning (RL) can be described by the grid world example.

We place one agent in an environment, the goal of the agent is to find a good route to the target. Every cell/grid the agent placed can be seen as a state. Agent can take one action at each state according to a certain policy. The goal of RL is to find a good policy to guide the agent taking a sequence of acitons, travelling from the start place, moving from one state to another, and finally reach the target.

grid world

Basic Concepts from the perspective of Markov decision process

Reinforcement learning utilizes the MDP framework to model the interaction between a learning agent and its environment. Actually the above example is just one simple description of the Markov decision preocess. It reflects how the agent interacts with the environment. The process directly involves three basic concepts state, action, policy and one transition state transition. It also implictly includes another concept reward.

We will introduce the key concepts one by one in the following.

State

State is the status of the agent with respect to the environment. Its set is the state space $S = {s_i}$.

Action

Action is what the agent do at a certain state. The agent will obtain a new state after taking one aciton. Similarly, its set is the action space of a state denoted as $A(s_i) = {a_i}$.

Policy

Policy denoted as $\pi$, tells the agent what actions to take at a state. It gives the probability of each action to be taken at a certain state denoted as $\pi(a_t|s_t)$. In mathematical form ,we use tabular representation to display one policy. In programming, we use one array, matrix to represent a policy.

tabular representation

Reward

Reward guides the agent toward the task objective. The agent aims to maximize expected cumulative return, whether rewards are positive or negative. For example, a return of -1 is better than -10. If the task is expressed in terms of costs instead, we minimize cumulative cost, or equivalently maximize its negative.

Reward can depend on the current state, action, and next state, for example $r(s,a,s')$. More generally, the joint distribution $p(s',r|s,a)$ describes both the next state and reward. Writing $r(s,a)=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$ means that the next-state and reward randomness have already been averaged out; it does not forbid rewards such as a bonus for reaching a goal.

Probability Distribution

Involve two probability form:

• State transition probability: at state $s$, taking action $a$, the probability to transit to state $s'$ is $p(s'|s,a)$

• Reward probability: at state $s$, taking action $a$, the probability to get reward $r$ is $p(r|s, a)$

Markov Property

Memoryless property: The state transiting to the next depends on current state and action rather than previous.

Other concepts

Trajectory and Return

A trajectory is a state-action-reward chain:

chain

The return of a trajectory is the sum of its rewards. For example, a finite episode with rewards $(0,0,0,1)$ has the undiscounted return below. If the episode is extended with an absorbing terminal state, all rewards after termination are zero.

$$return = 0 + 0 + 0 + 1 = 1$$

Return can be used to evaluate a policy.

Discounted Rate

The discount factor is usually $\gamma\in[0,1)$ for continuing tasks. Finite-horizon episodic tasks can also use $\gamma=1$.

With bounded rewards, $\gamma<1$ keeps an infinite discounted sum finite. It also controls the relative weighting of near and distant rewards:

• If $γ$ is close to 0, the value of the discounted return is dominated by the rewards obtained in the near future.

• If $\gamma$ is close to 1, distant rewards decay more slowly. They do not necessarily dominate the return, since their magnitudes also matter.

The first reward has exponent zero:

$$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots.$$

For a continuing reward sequence $(0,0,0,1,1,\ldots)$, this gives

$$G_t=0+\gamma\cdot0+\gamma^2\cdot0+\gamma^3\cdot1+\gamma^4\cdot1+\cdots=\frac{\gamma^3}{1-\gamma}.$$

If the episode instead terminates after the first reward of 1, the discounted return is just $\gamma^3$.

Episode

When interacting with the environment following a policy, the agent may stop at some terminal states. The resulting trajectory is called an episode (or a trial), e.g. $s_1 \to s_2 \to s_3 \to s_5$,

An episode is usually assumed to be a finite trajectory. Tasks with episodes are called episodic tasks.

Two common ways to model a goal state should be distinguished:

• Option 1: Treat the target state as a special absorbing state. Once the agent reaches an absorbing state, it will never leave. After the reward for the terminal transition, all subsequent rewards are zero. This preserves the return of the original episodic task.

• Option 2: Treat the target state as a normal state with a policy. The agent can still leave the target state and gain r = +1 when entering the target state. This generally defines a different, continuing task because the agent can collect the goal reward repeatedly.

The grid-world examples in this tutorial use option 2 and treat the target as an ordinary state. It should not be confused with the zero-reward absorbing-state extension of an episodic task.