Reinforcement Learning

Reinforcement Learning: the program learns from consequences of its actions (reward or punishment), rather than from being explicitly taught and selects its actions on basis of its past experiences (exploitation) and also by new choices (exploration).

Link to original

Summary of RL

An agent occupies a given state at any given time. An action moves the agent from one state to another. In RL, there is no human interaction. The agent is placed into an environment and is given a goal to learn how to behave in the environment by trial and error using feedback from its own actions and experiences.

The agent needs to know that something good or bad has happened, this kind of feedback is called a reward or reinforcement.

Characteristics of RL:

• goal-oriented learning
• interaction with an uncertain environment
• learning how to map situations to actions to maximise numerical reward signal
• learner is not told which actions to take
• trial and error search
• possibility of delayed reward
• exploration vs. exploitation

RL works with evaluative feedback which says how good the action was and not whether it was the best thing to do (instruction feedback).

Associative learning maps inputs to outputs and learns best output for each input, while non-associative learns the one best output.

$n$-armed bandits

$n$-armed bandits is a situation where:

• We have $n$ actions to choose from, where reward probabilities are not known.
• Our goal is to maximise the total reward in the long run.

We can take the following approach:

• Choose repeatedly from one of $n$ actions. (each choice is called a play)
• Action values: after each play $a_t$, you get a reward $r_t$, where $E⟨r_t|a_t⟩=Q^{\ast }(a)$
  • Distribution of $r_t$ depends only on $a_t$.
• Our objective is to maximise reward in long term, so to solve the $n$-armed bandit problem, we must explore a variety of options and then exploit the best of them.

Exploration vs. exploitation

Suppose we form action value estimates (what each action is worth at each point in time) $Q_t(a)\text{ which estimates }{Q}^{\ast }(a)$ Given we maintain a $Q_t(a)$ estimate for every $a$, then there is (at least) one action whose estimated value is greatest at any time step (greedy).

The greedy action at $t$ is: $a_t^{\ast }=\arg {\max }_a{Q}_t(a)$ Picking $a_t^{\ast }$ is exploitation, any other value is exploration. Exploitation will maximise the expected reward on one step but exploration may produce the greater total reward in the long run. We cannot do both at the same time. Exploration is generally infinite but we should eventually reduce exploring.

Action-value methods

“Sample-average” method: maintain a list of all rewards received and average them for each action

• If by the $t$-th play, action $a$ has been chosen $k_a$ times prior to $t$, yielding $r_1,r_2,\dots r_{k_a}$: $Q_t(a)=\frac{r_1+r_2+\dots +r_{k_a}}{k_a}$
• If $k_a=0$, then set $Q_t(a)$ to some default value, e.g. $Q_1(a)=0$.
• If we update often enough, the estimate of the value of each action will converge to the actual value of the action. ${\lim }_{k_a\to \infty }{Q}_t(a)=Q^{\ast }(a)$
• However, this method uses too much memory, so we use an incremental implementation.

Incremental implementation: if $Q_k$ is the average of the first $k$ rewards and $r_{k+1}$ is the $k+1\text{ th}$ reward, then $\begin{array}{rl}{Q}_{k+1}& =\frac{1}{k+1}\sum _{i=1}^{k+1}{r}_i\\ & =\frac{1}{k+1}(r_{k+1}+\sum _{i=1}^k{r}_i)\\ & =\frac{1}{k+1}(r_{k+1}+k{Q}_k)\\ & =\frac{1}{k+1}(r_{k+1}+k{Q}_k+Q_k-Q_k)\\ & =\frac{1}{k+1}(r_{k+1}+(k+1)Q_k-Q_k)\\ & =Q_k+\frac{1}{k+1}(r_{k+1}-Q_k)\end{array}$

$ϵ$-greedy gives us a way to balance exploration-exploitation.

• Pick $ϵ\ll 1$
• $e$-greedy action selection: $a_t=\{\begin{array}{ll}{a}_t^{\ast }& \text{with probability }1-ϵ\\ \text{random action}& \text{with probability }ϵ\end{array}$
• Most of the time we are greedy, but explore sometimes. This is the simplest way to try to balance exploration and exploitation.