The basic idea

• Reinforcement learning: the problem of how an agent figures out how it can act in an environment so as to maximize long-term reward
• The simplest case: all reinforcements are immediate.
  • Like supervised learning in the reward case
  • In the punishment case, there is no information about what should have been done
• The more realistic case: reinforcements happen only sometimes
  • The temporal credit assignment problem: when was/were the action(s) taken that led to the reinforcement received?
  • In extreme cases, reinforcement only at the "end" (board games like backgammon and chess)
• Markov decision processes

  

  • States and actions
    • The "real" state of the agent and what it "thinks" its state is
    • Actions take agents from one state to another.
    • In each state there is a set of actions to choose from.
  • Discrete time
  • Reinforcements
    • Rewards and punishments
    • Reinforcements depend only on the current state and the action taken.
    • The reinforcement function is built into the environment and is not known to the agent; it may be non-deterministic.
  • The next-state function
    • Function of the current state and the action.
    • The next-state function is built into the environment and is not known to the agent; it may be non-deterministic.
    • The actual value of a state and what the agent thinks the value is
    • The actual value of an action in a given state and what the agent thinks the value is (Q-values)
• Policies
  • A policy maps states into actions the agent ought to take in those states
  • The goal of RL is to learn a policy that maximizes the sum of future reinforcements
  • The problem of delayed reinforcement (the temporal credit assignment problem): how to choose an action in a state where there will be no reinforcement
• Learning
  • Long-term memory: the agent's record of what it has learned about the environment
  • Learning: updating the long-term memory on the basis of new information from the environment
  • The importance of learning in small steps, controlled by the learning rate
• How the agent uses its knowledge
  • Exploitation: relying on what's been learned
  • Exploration: behaving stochastically; trial-and-error

Q learning

• Q learning tries to find a value for each pair of a state (s) and an action (a).
  • Each Q-value is a function of a state and an action: `Q(s, a)`.
  • The Q-value for a given s, a pair needs to be based on the reinforcement that the environment gives the agent when the agent performs a in s (that is, what the environment's reinforcement function returns).
  • But sometimes there's no reinforcement; instead an action may make a future reinforcement possible.
  • So the Q-value also needs to somehow take into account what happens in the next state (that is, what the environment's next-state function returns).
• The trick
  • The basic idea: take the Q-value to be the sum of all future reinforcements received by the agent when taking that action and then following its policy.
  • The agent can't know this, so it has to estimate it, treating the Q-value of a state-action pair recursively. The value is (a function of)
    • the immediate reinforcement received and
    • (what the agent currently believes to be) the value of the best action in the new state that is reached.
  • So at any given point during learning, the agent has an estimate of the values for all state-action pairs. On a given learning trial, the agent is in state `s_t`. It does the following.
    • Selects an action `a_t` and executes it.
    • Notes whatever reinforcement it receives as a result: `r(s_t, a_t)`
    • Notes what new state it is in: `s_{t+1}`
    • Finds what it believes to be the value of the best action in the new state: `Q^{best}(s_{t+1}, a)`
    • Combines 2 and 4 to update its estimated value for the pair `s_t`, `a_t`
• Discounting the next state estimate
  • Just adding the reinforcement to the estimated next state value causes problems if the future reinforcements are infinite.
  • Usually it is the discounted best value of the next state that is added, that is, that estimate times a discount rate γ.
  • So we could update the Q-value for a state-action pair using this update equation:
    `Q(s_t, a_t) = r(s_t, a_t) + gamma max_{a_(t+1)} Q(s_{t+1}, a_{t+1})`
    The expression beginning with "max" means for all of the possible actions in the next state, `a_(t+1)`, the highest of the Q values that the agent has stored for that state in its LTM.
• Learning rate
  • But the information we get on a given learning trial may be misleading, so this update equation moves too quickly.
  • Instead we usually move relatively slowly in the direction indicated by the current evidence; that is, there is a learning rate (η), which controls the step size of the learning. With this, the update equation is:
    `Q^{t+1}(s_t, a_t) = (1-eta) Q^t(s_t,a_t) + eta [r(s_t, a_t) + gamma max_{a_(t+1)} Q^t(s_{t+1}, a_{t+1})]`
    This equation combines the old knowledge that the agent has with the new information coming from the current experience of receiving a reinforcement and ending up in a new state.

An example: maze

• 

• s	a	r	Q							new
  			1,r	1,s	2,r	2,l	3,r	3,l	G,s
  1	r	0	0	0	0	0	0	0	0
  2	r	0
  3	r	1
  G	s	0
  1	r	0
  2	r	0
  3	r	1
  G	s	0

  γ = .8, η = .5 and all values initialized at 0. In the chart, "new" means the reinforcement received plus the discounted maximum value of the next state. The "new" value is combined with the "old" using the learning rate to give the updated Q-value appearing in the next line of the chart.

• s	a	r	Q							new
  			1,r	1,s	2,r	2,l	3,r	3,l	G,s
  1	r	0	0	0	0	0	0	0	0	0
  2	r	0	0	0	0	0	0	0	0	0
  3	r	1	0	0	0	0	0	0	0	1
  G	s	0	0	0	0	0	.5	0	0	0
  1	r	0	0	0	0	0	.5	0	0	0
  2	r	0	0	0	0	0	.5	0	0	.4
  3	r	1	0	0	.2	0	.5	0	0	1
  G	s	0	0	0	.2	0	.75	0	0	0

Another example: ALife

• States (texture of cell in front of critter): Empty (black), Soft (green), Hard (yellow)
• Actions: MOVE, TURN, EAT
• Reinforcements
  • Moving: -1
  • Turning: -1
  • Bumping into something: -5
  • Eating a plant: 10
  • Eating a rock: -10
  • Eating nothing (emptiness): -1
• Q values

  		a
  		MOVE	TURN	EAT
  s	EMPTY
  	SOFT
  	HARD

• A sequence of states and actions

  TURN	MOVE	MOVE	EAT	EAT	MOVE
  TURN	EAT	EAT	MOVE	EAT

Making decisions

• How is the agent to pick an action?
• The exploration-exploitation tradeoff revisited
  • Exploitation: pick the action that has the highest Q-value for the current state
  • But the agent can only learn about the value of actions that it tries; it should try a variety of actions, including actions other than the ones it thinks are best: exploration.
  • Exploration makes more sense early on in learning when the agent doesn't know much; the probability of exploration should decrease with experience.
• One simple possibility for selecting an action
  • Pick the "best" action with probability `P_{text(exploit)} = 1 - e^{-E*A}`, where A is the number of training samples (the "age" of the agent) and E is a constant.
  • With E = 0.1 and E = 0.01,
      
• A smarter possibility
  • Have the probability of picking an action depend on how high its value is relative to the values of all of the other possible actions; that is, use the Luce choice rule.
  • One way to do this; there is now a separate exploitation probability for each action `a^i`:
    `P_{text(exploit)}(a_t^i) = (e^{E * A * Q(s_t, a_t^i)}) / (sum_a e^{E * A * Q(s_t,a_t)})`
  • But as learning progresses, the variance among the Q-values should increase, increasing the probability of exploitation, even if the probability is not a function of "age". So it's possible to leave out the `A` in the equation.

Implementation

• We can implement the Q-values for each combination of state and action as a matrix, that is, a list of lists.
• On each time step, the agent is in a particular state, corresponding to one list within the Q-value list of lists; that is, each state must be an integer.
• The agent selects an action and can then update one cell in the matrix, that is, one number in the list for the state (well, not yet, as it turns out).
• That is, each action must also be represented as an integer.
• Here's what has to happen on a time step t:
  • The agent senses where it is, yielding a state s_t, that is, an integer.
  • The agent selects an action a_t (also an integer), using one of the methods discussed on the page on making decisions.
  • The agent executes the action, receiving a reinforcement r (s_t, a_t) from the world and moving to a new state (though it doesn't know what this is yet because it hasn't called its sensor).
  • The agent updates the Q-value for the previous state-action pair, s_t-1, a_t-1, using the previous reinforcement as well, r (s_t-1, a_t-1) (now that it knows what the next state is for this pair). These must have been saved in variables.
  • Finally it updates the variables where the previous state, action, and reinforcement are stored, reassigning them to the current state, action, and reinforcement.

A sketch of how Q learning will be implemented

def step(self):
    """Sense, decide what to do, act, and learn."""
    # Reinitialize reinforcement
    self.reinforcement = 0

    # Get sensory input
    state = self.sensory_state()
    # Get the critter's current Q-values for this state
    q_values = self.get_Q(state)

    # Update reinforcement for sensing cost and cost of step
    self.reinforcement += self.sense_reinforce()
    self.reinforcement += self.step_cost

    # Select action
    action_index = self.decide(q_values)

    # Execute action and increment reinforcement based on what happens
    self.reinforcement += self.index2action(action_index)()

    # Q learning
    if self.world.n_steps != 0:
        self.learn(state, q_values)
    self.last_reinf = self.reinforcement
    self.last_state = state
    self.last_action = action_index

    # Update strength
    self.strengthen(self.reinforcement)