Q-learning

Reinforcement learning involves an agent, a set of states ${\displaystyle S}$, and a set ${\displaystyle A}$ of actions per state. By performing an action ${\displaystyle a\in A}$, the agent transitions from state to state. Executing an action in a specific state provides the agent with a reward (a numerical score).

The goal of the agent is to maximize its total reward. It does this by adding the maximum reward attainable from future states to the reward for achieving its current state, effectively influencing the current action by the potential future reward. This potential reward is a weighted sum of the expected values of the rewards of all future steps starting from the current state.

As an example, consider the process of boarding a train, in which the reward is measured by the negative of the total time spent boarding (alternatively, the cost of boarding the train is equal to the boarding time). One strategy is to enter the train door as soon as they open, minimizing the initial wait time for yourself. If the train is crowded, however, then you will have a slow entry after the initial action of entering the door as people are fighting you to depart the train as you attempt to board. The total boarding time, or cost, is then:

• 0 seconds wait time + 15 seconds fight time

On the next day, by random chance (exploration), you decide to wait and let other people depart first. This initially results in a longer wait time. However, time fighting other passengers is less. Overall, this path has a higher reward than that of the previous day, since the total boarding time is now:

• 5 second wait time + 0 second fight time.

Through exploration, despite the initial (patient) action resulting in a larger cost (or negative reward) than in the forceful strategy, the overall cost is lower, thus revealing a more rewarding strategy.

Q-Learning table of states by actions that is initialized to zero, then each cell is updated through training.

After ${\displaystyle \Delta t}$ steps into the future the agent will decide some next step. The weight for this step is calculated as ${\displaystyle \gamma ^{\Delta t}}$, where ${\displaystyle \gamma }$ (the discount factor) is a number between 0 and 1 (${\displaystyle 0\leq \gamma \leq 1}$) and has the effect of valuing rewards received earlier higher than those received later (reflecting the value of a "good start"). ${\displaystyle \gamma }$ may also be interpreted as the probability to succeed (or survive) at every step ${\displaystyle \Delta t}$.

The algorithm, therefore, has a function that calculates the quality of a state-action combination:

${\displaystyle Q:S\times A\to \mathbb {R} }$ .

Before learning begins, ${\displaystyle Q}$ is initialized to a possibly arbitrary fixed value (chosen by the programmer). Then, at each time ${\displaystyle t}$ the agent selects an action ${\displaystyle a_{t}}$, observes a reward ${\displaystyle r_{t}}$, enters a new state ${\displaystyle s_{t+1}}$ (that may depend on both the previous state ${\displaystyle s_{t}}$ and the selected action), and ${\displaystyle Q}$ is updated. The core of the algorithm is a Bellman equation as a simple value iteration update, using the weighted average of the old value and the new information:

${\displaystyle Q^{new}(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}-\underbrace {Q(s_{t},a_{t})} _{\text{old value}}{\bigg )}} ^{\text{temporal difference}}}$

where ${\displaystyle r_{t}}$ is the reward received when moving from the state ${\displaystyle s_{t}}$ to the state ${\displaystyle s_{t+1}}$, and ${\displaystyle \alpha }$ is the learning rate (${\displaystyle 0<\alpha \leq 1}$).

Note that ${\displaystyle Q^{new}(s_{t},a_{t})}$ is the sum of three factors:

• ${\displaystyle (1-\alpha )Q(s_{t},a_{t})}$: the current value weighted by the learning rate. Values of the learning rate near to 1 made faster the changes in Q.
• ${\displaystyle \alpha \,r_{t}}$: the reward ${\displaystyle r_{t}=r(s_{t},a_{t})}$ to obtain if action ${\displaystyle a_{t}}$ is taken when in state ${\displaystyle s_{t}}$ (weighted by learning rate)
• ${\displaystyle \alpha \gamma \max _{a}Q(s_{t+1},a)}$: the maximum reward that can be obtained from state ${\displaystyle s_{t+1}}$(weighted by learning rate and discount factor)

An episode of the algorithm ends when state ${\displaystyle s_{t+1}}$ is a final or terminal state. However, Q-learning can also learn in non-episodic tasks. If the discount factor is lower than 1, the action values are finite even if the problem can contain infinite loops.

For all final states ${\displaystyle s_{f}}$, ${\displaystyle Q(s_{f},a)}$ is never updated, but is set to the reward value ${\displaystyle r}$ observed for state ${\displaystyle s_{f}}$. In most cases, ${\displaystyle Q(s_{f},a)}$ can be taken to equal zero.

Q-learning at its simplest stores data in tables. This approach falters with increasing numbers of states/actions since the likelihood of the agent visiting a particular state and performing a particular action is increasingly small.

Q-learning was introduced by Chris Watkins[11] in 1989. A convergence proof was presented by Watkins and Dayan[12] in 1992.

Watkins was addressing “Learning from delayed rewards”, the title of his PhD thesis. Eight years earlier in 1981 the same problem, under the name of “Delayed reinforcement learning”, was solved by Bozinovski's Crossbar Adaptive Array (CAA).[13][14] The memory matrix W =||w(a,s)|| was the same as the eight years later Q-table of Q-learning. The architecture introduced the term “state evaluation” in reinforcement learning. The crossbar learning algorithm, written in mathematical pseudocode in the paper, in each iteration performs the following computation:

• In state s perform action a;
• Receive consequence state s’;
• Compute state evaluation v(s’);
• Update crossbar value w’(a,s) = w(a,s) + v(s’).

The term “secondary reinforcement” is borrowed from animal learning theory, to model state values via backpropagation: the state value v(s’) of the consequence situation is backpropagated to the previously encountered situations. CAA computes state values vertically and actions horizontally (the "crossbar"). Demonstration graphs showing delayed reinforcement learning contained states (desirable, undesirable, and neutral states), which were computed by the state evaluation function. This learning system was a forerunner of the Q-learning algorithm.[15]

In 2014 Google DeepMind patented[16] an application of Q-learning to deep learning, titled "deep reinforcement learning" or "deep Q-learning" that can play Atari 2600 games at expert human levels.

The standard Q-learning algorithm (using a ${\displaystyle Q}$ table) applies only to discrete action and state spaces. Discretization of these values leads to inefficient learning, largely due to the curse of dimensionality. However, there are adaptations of Q-learning that attempt solve this problem such as Wire-fitted Neural Network Q-Learning.[22]

• Reinforcement learning
• Temporal difference learning
• SARSA
• Iterated prisoner's dilemma
• Game theory

• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
• Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
• Piqle: a Generic Java Platform for Reinforcement Learning
• Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning.
• Q-learning work by Gerald Tesauro