Reinforcement Learning

Firstly, we assume that all the environments in the following materials are all modeled by Markov decision processes. As we have known, an MDP model can be represented by a tuple $(S,A,T,R)$, the rewards are returned from the environment after each step, or sometimes they are returned only at the end of the game. No matter how frequent we can get a reward from environment, they can help the agent to learn a better policy, so the reward is also called reinforcement here. So, reinforcement learning aims to use observed rewards to learn an optimal (or nearly optimal) policy that maximizes expected total reward for the environment.

In most situations, we assume no knowledge of the model for the environment (transition function) or the reward function.

Prediction and Control

Usually, in learning problems, we are not given the model and have to use observed data. There are two main parts for a learning problem:

• Prediction problem: for a fixed policy $\pi$, to learn the value $V$ or action-value $Q$ from the observed data by executing the policy. In this part, we want to learn to model the environment, namely, learn how the environment works.
• Control problem: to learn the policy $\pi$. In this part, we want to find an optimal policy based on our observed data and our current knowledge of the environment.

The two parts suport each other, one learns the environment and another one learns the policy.

Exploration and Exploitation

The two parts of the learning problem can also be understood in another aspect. Since mostly, we don’t know clearly about the environment (the transition model and the reward function), so one important thing is to learn about the environment, namely, explore the environment; once we have some knowledge about how it works, we will try to exploit what we have learnt. How to trade the exploration and exploitation off is a very important thing.

A very classic example is the multi-armed bandit. To make things simple, we suppose there are only two arms on the bandit, with differnet and unknown probability of how likely you can get a reward at one play. To illustrate the problem, we now set the probability of the two arms as the following table, note that we actually don’t know these probabilities, just like we don’t know about an environment.

Arm	Probability of Getting 10-Dollar Reward
Arm 1	0.3
Arm 2	0.8

Now, suppose you have 1000 chances to choose pull one of the arm and you want to get a highest cumulative reward, what should you do?

• Exploration: for some chances, you randomly choose one of the arm and record the times you get the reward, then based on the experiences, you will more precisely approximate the behind probability of each arm, just like the sampling experiment.

• Exploitation: for some chances, based on your estimated probability, you will always choose the arm with higher proability of getting reward.

However, you may feel hesitant, if you use more chances to explore, you get a more precise estimation, but there will be less chances left for you to exploit your higher-probability arm; if you use few chances to explore, you indeed have more chances to explit your knowledge, but you may not get an accurate estimation, so you may always choose the arm with lower probability. This is the exploration vs exploitation dilemma.

In reinforcement learning, actions interacting with the environment not only gain reward but also help to learn a better model, by improving the model, greater reward may potentially be obtained. A scheme called greedy in the limit of infinite exploration (GLIE) for balancing exploration and exploitation must:

• Try each action in each state an unbounded number of times to avoid a finite probability of missing an optimal action
• Eventually become greedy so that it is optimal with respect to the true model

One simple GLIE scheme is to do $ϵ$-greedy exploration with choice of $ϵ=\frac{1}{t}$, $ϵ$-greedy exploration means that choose the greedy action (explotiation) with probability $1-ϵ$ and a random action (exploration) with probability $ϵ$. And here, we set the $ϵ$ to graudally decrease with time, then it becomes one of the GLIE scheme.

Model-Based RL Method

In model-based prediction, we try to learn the model and solve it. This method needs the agent firstly model the environment, namely, to learn the transition model $P(s^{\prime }|s,a)$ and reward function $R(s,a,s^{\prime })$, so it can calculate the values by doing policy evaluation stated in the earlier chapters (solve linear equations or use iterative method).

Learning the transition model and the reward function can be done easily using sampling. For example, we did $N$ times of experiments, we notice that there are $M$ times for the environment transit from state $s_a$ to $s_b$ after taking action $a$ and get reward $r$ in average, then we can approximately set the transition function $P(s_b│s_a,a)=\frac{M}{N}$ and the reward function $R(s_a,a,s_b)=r$. The more experiments we do, the more accurate we can model the environment.

Once we have modeled the environment, then the agent can learn an optimal policy using basic Adaptive Dynamic Programming (ADP) method. Evenly, if the environment is deterministic (all transition probability equals to 1), then simply using greedy algorithm by choosing the action leading to the highest value can be the optimal policy.

Finally, model-based method is based on modeling the environment and solving the model. (Evenly, for some situations that we know the model in advance, it becomes much more easier). Conversely, a model-free method considers learning the value function directly without learning the transition and reward functions, namely, it doesn’t model the environment any more.