Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Value and policy iteration need the transition model . Often it is not known. Reinforcement learning learns a good policy from experience (observed states, actions and rewards) instead.
TD Prediction
The prediction (policy evaluation) problem: for a given policy , estimate the state value function .
The simplest method, TD(0), updates after every single step:
Where:
- is the learning rate
- is the TD target, an estimate of the return
- the bracket is the TD error, how surprised the agent is by what happened
The agent nudges its old estimate towards the target, using its own current estimate of the next state (bootstrapping).
Advantages of TD Learning
Compared with model based methods and with waiting for the end of an episode:
- needs no model of the environment, only experience
- fully incremental: learns before knowing the final outcome, with less memory and less peak computation
- can learn without a final outcome, i.e. from incomplete sequences
Q-Learning
Not in the slides, but the action version of TD used in practice (and named in the data science part under adaptive learning). It learns action values directly, so a policy can be read off without a model:
The greedy policy is . While learning, the agent usually explores with an -greedy rule (random action with probability ).
import random
def q_learning_step(Q, s, actions, env_step, alpha=0.1, gamma=0.9, eps=0.1):
a = random.choice(actions) if random.random() < eps \
else max(actions, key=lambda x: Q[(s, x)])
r, s2 = env_step(s, a) # act, observe reward and next state
target = r + gamma * max(Q[(s2, x)] for x in actions)
Q[(s, a)] += alpha * (target - Q[(s, a)])
return s2Application
NTU's team HogRider won the 2017 Microsoft Malmo Collaborative AI Challenge (a "stag hunt" game in Minecraft, over 80 teams) by combining learning, game theoretic reasoning and sequential decision making.
The quantity TD estimates is the state utility defined in Markov Decision Processes.