Robot learning

1. Machine learning in one slide

There exist problems for which it is extremely difficult to write programs that solve them satisfactorily: programs might be horrendously complicated, might lack generality, might not work for noisy data, and probably need to be frequently updated. The solution: use programs/systems that learn from experience. Instead of writing a program by hand for each specific task, we collect lots of examples that specify the correct behaviour; a machine learning algorithm takes these examples and produces a program that does the job. The resulting program might look very different from a handwritten one; if we do it right, it works also for new cases (generalisation); and if data change, the program can change too by training on new data.

2. The three learning paradigms

Reinforcement learning addresses the question of how an autonomous agent that senses and acts in its environment can learn to choose optimal actions to achieve its goal — which makes it the paradigm of choice for robots, where behaviour unfolds in time and the consequences of an action arrive after the action.

3. What a learning robot needs

The requirements for learning robots (sometimes not met, or only partially met):

• Noise immunity — sensors and actuators are noisy;
• Fast convergence — the robot cannot wait forever;
• On-line learning — learning while operating;
• Incremental learning — integrating new experience without forgetting the old;
• Tractability — the computation must fit the hardware;
• Situatedness — learning should be based on the robot's view of the world (Chapter 1: only through its sensors).

The most common type of learning in natural and artificial systems is associative learning: the robot learns about the relationship (a) between two stimuli, or (b) between a stimulus and a response. Case (a) is classical conditioning (Pavlov's experiments); case (b) is reinforcement learning, also called operant conditioning.

4. Associative learning: conditioning and Hebb's rule

Classical conditioning is unsupervised, with typical learning rules the Hebb rule and the Kohonen rule. The Hebb rule: Hebbian learning strengthens the connection between two neurons if they are active at the same time. In artificial neural systems:

Δwi = η · oj · oi

where η is the learning rate and o_i, o_j the outputs of neurons i and j.

Example: Distributed adaptive control

The goal is to associate the stimuli from proximity sensors with avoidance behaviour through collision reflexes. Collision sensors activate the wheels such that the robot goes away (hardcoded neural connections). Each time a collision takes place, Hebbian learning is applied to strengthen the connections that were active at the same time — hence connections between proximity sensor neurons and collision ones are strengthened. After some collisions, the inputs from proximity sensor neurons are high enough to activate collision neurons even without a collision: (a) the robot learns the association between "moving away" and "close obstacles"; (b) if a target sensor is added, the goal-oriented behaviour with obstacle avoidance can be achieved.

5. Reinforcement learning: the MDP formulation

RL learns a mapping from perceived states to desired actions — a policy — that maximises system performance at the particular task assigned. The fundamental assumption: robot-environment interactions can be modelled as a Markov Decision Process (MDP) — both the robot and the environment can be modelled as probabilistic FSMs acting at discrete time steps (the bridge to Chapter 6). The qualifier "Markov" means the transition probabilities and reward functions depend on the past only through the current state and the action selected in it.

The RL learning scheme: the robot can perceive a finite set S of distinct states and has a finite set A of actions. At each discrete time step t the robot senses the current state s_t, chooses an action a_t and performs it; the environment responds by giving the reward r_t = r(s_t, a_t) and producing the succeeding state s_t+1 = δ(s_t, a_t). The functions r and δ are not known to the robot. In practice the robot might not receive a reward every step, and the reward is likely to come with a delay with respect to the actions taken — the problem of temporal credit assignment: determining which of the actions in the sequence are to be credited with producing the eventual rewards.

The infinite horizon discounted model

The policy is a function from states to actions, π : S → A. We define V^π(s_t) as the cumulative value achieved by following π from initial state s_t. The typical model is the infinite horizon discounted model:

Vπ(st) = Σ_{i=0..∞} γ^i · r_{t+i}

where γ ∈ [0,1] is the discount factor (0⁰ ≡ 1). Rewards far in the future are normally less trusted than the current one and those in the near future; moreover, the final outcome of a strategy often strongly depends on the first choices. The learning task: find the optimal policy π* that maximises V^π(s) for all states s.

How to find it: the robot should prefer state s₁ over s₂ whenever V*(s₁) > V*(s₂) — but the policy must choose among actions, not among states. The optimal action in state s is the action a that maximises the sum of the immediate reward r(s,a) plus the value V* of the immediate successor state, discounted by γ:

π*(s) = argmax_a [ r(s, a) + γV*(δ(s, a)) ]

If the robot knew r and δ (the typical case of a fully specified MDP), it could compute the optimal action for any state. Unfortunately the robot does not know r and δ. Is there an alternative evaluation function the robot can learn by exploiting its experience? Yes: Q-learning.

6. Q-learning

The robot learns an action–value function Q(s, a), which it uses to evaluate the utility of performing action a in state s: Q(s,a) is defined as the return the robot expects to receive given that it starts in state s and follows the optimal policy π* thereafter:

Q(s, a) ≡ r(s, a) + γV*(δ(s, a))

As V*(δ(s,a)) is the highest utility one can get from the successor state, the definition can be rewritten recursively:

Q(s, a) ≡ r(s, a) + γ · max_{a'} Q(δ(s, a), a')

Hence the best action in state s is the one that maximises Q: π*(s) = argmax_a Q(s, a). It may seem surprising that one can choose globally optimal action sequences by reacting repeatedly to the local values of Q for the current state — no lookahead search is ever needed, because the value of Q for the current state and action summarises in a single value all the information needed to determine the discounted cumulative reward that will be gained in the future if action a is selected in state s.

The Q-learning algorithm iteratively manipulates an estimate Q̂:

For each (s, a) initialize the table entry Q̂(s, a) to zero
Observe the current state s
Repeat until termination condition not reached:
   Select an action a and execute it
   Receive immediate reward r
   Observe the new state s′
   Update the table entry for Q̂(s, a):
      Q̂(s, a) ← (1 − α)Q̂(s, a) + α[ r + γ max_{a′} Q̂(s′, a′) ]
   s ← s′

α is the learning rate: how much the old Q-values are taken into account in the update. If α is very high, the robot's prior knowledge is almost entirely ignored; if α is small, a lot of weight is given to past experience. The intuition: each time the robot moves forward from an old state to a new one, Q-learning propagates Q estimates backward from the new state to the old, augmented by the immediate reward; given enough training episodes, information propagates from the transitions with nonzero reward back through the entire state-action space. The recursion is guaranteed to converge under easily satisfiable hypotheses.

7. Exploration vs exploitation

Q-learning's action selection is the typical case of the exploration/exploitation tradeoff. At one extreme, actions are chosen randomly (pure exploration); at the other, we choose the action with the highest Q̂ (pure exploitation). Better to choose probabilistically. A possible way:

P(ai | s) = Q̂(s, ai)^k / Σ_j Q̂(s, aj)^k

The exponent k determines how strongly selection favours actions with high Q̂: larger values assign higher probabilities to above-average actions (exploit what has been learned); small values allow higher probabilities for other actions (explore). In some cases k is varied with the number of iterations — favour exploration early, gradually shift toward exploitation. An alternative: ε-greedy — pick a random action with probability ε, choose the action that maximises Q̂ with probability 1 − ε, tuning ε along the process from high to low values.

8. Extensions and related families

• Simple learning algorithm, but it requires discrete states and has slow convergence; Q̂-values tend to the true distribution of rewards and the policy yields maximum reward.
• Extensions to continuous domains (e.g. actor-critic with continuous actions, function approximation).
• Sometimes used to improve a given policy — e.g. one learned by imitation.
• Often combined with ANNs → Deep RL (the Q-function approximated by a neural network).
• Feature-based representations to generalise across states: approximate the value with a weighted sum of features, V(s) = w₁f₁(s) + ... + w_nf_n(s), and similarly for Q̂(s,a).

9. Actor-critic methods

Actor-critic methods have a separate memory structure to explicitly represent the policy independent of the value function. The policy structure is known as the actor, because it is used to select actions; the estimated value function is known as the critic, because it criticises the actions made by the actor. Typically the critic is a state-value function: after each action selection, the critic evaluates the new state to determine whether things have gone better or worse than expected; the critique takes the form of a temporal difference (TD) error — a scalar signal that is the sole output of the critic and drives all learning in both actor and critic.

10. Inverse reinforcement learning

Inverse reinforcement learning (IRL) is the problem of inferring the reward function of an agent, given its policy or observed behaviour (Arora & Doshi, 2021). The learned reward function can then be used to generate a policy that reproduces the demonstrated behaviour. IRL is motivated by the fact that, for some classes of problems, demonstrating an optimal behaviour is easier than defining a reward function — and the same difficulty was already flagged for objective functions in Chapter 11. As Russell pointed out, the reward function is also inherently more transferable than the policy: even slight changes in the environment (e.g. noise levels in the transition function) likely render a learned policy unusable, while the reward function survives and simply needs to be extended to any new states.

In IRL, the reward function R of the agent's MDP is not provided; demonstrations of the desired behaviour are given in the form of sequences of states, and it is assumed that a "true" reward function R* exists such that the policy π* that maximises the value function based on R* would generate the given demonstrations. Ng and Russell (1998) gave the foundational formulation and algorithms. Apprenticeship learning (Abbeel & Ng, 2004) is the most influential practical variant: it assumes a feature map φ : S → [0,1]^k from states to a k-dimensional vector of features, and works with feature expectations µ(π) — the expected discounted cumulative feature vector under a policy. The algorithm:

Apprenticeship learning (Abbeel & Ng 2004)
Given: φ, µE (the feature expectation of the expert)
Select a random initial policy π0
Compute µ0 := µ(π0)
repeat
   Compute w_{i+1} by fitting a SVM on µE and all µi
   Learn policy π_{i+1} on rewards R_{i+1}(s) = w_{i+1} · φ(s)
   Compute µ_{i+1} := µ(π_{i+1})
until stopping criterion met
return w_{i+1} as w*

At every iteration, a support vector machine is fitted on the expert's feature expectation and all encountered ones; its coefficients define the weight vector w that specifies the reward function; a new policy is learned on that reward; the process stops when the current policy's behaviour is sufficiently close to the demonstrations. The well-known application that brought attention to IRL: helicopter flight control — an expert helicopter operator's preferences over 24 features were learned from recorded behaviour, and the reward was used to teach a physical remote-controlled helicopter advanced manoeuvres with RL. Other applications: socially adaptive navigation (learning from human walking trajectories), route prediction for taxis, driving styles.

11. IRL meets automatic design: Demo-Cho

The Robot learning deck closes with the link to Chapter 11, and the IRIDIA group made it concrete: the problem of defining an objective function is similar to the one of defining a reward function in reinforcement learning — so RL can be adopted in the framework of the automatic design of control software for robot swarms: instead of defining a mission-specific objective function, provide demonstrations of the desired swarm behaviour and let an IRL algorithm infer an objective function to automatically generate the control software that produces the desired behaviour itself.

Demo-Cho (Gharbi, Kuckling, Garzón Ramos & Birattari, ICRA 2023) combines inverse reinforcement learning with automatic modular design: apprenticeship learning is used to infer a reward function from demonstrations, and Chocolate (Chapter 11) then designs the control software that optimises it. The focus is on missions in which what the robots should accomplish is to position themselves in the environment according to a desired distribution — in this class, a demonstration is simply the desired final configuration of the robots, which an untrained end user can specify without mathematical modelling. Only on the basis of demonstrations, and without an explicit objective function, Demo-Cho successfully generated control software for four missions, in simulation and with physical robots. It is the endpoint of a chain the course built in order: reward definition is hard (Chapter 12) exactly like objective-function definition is hard (Chapter 11) — and the solution is to let demonstration stand in for specification.

12. Lab activity: Q-learning path following in ARGoS

One of the most common tasks for robots in real-world contexts is to follow a path: for instance, moving objects to target areas while constraining the path by following a trace painted on the ground (the path is assumed always free, so no collision issues). The robot is equipped with ground sensors and uses these values to define its trajectory. One could write a control program by hand — but this is also an interesting context to try RL.

The handout provides a Q-learning implementation for path following in ARGoS (code by Matteo Magnini, with minor changes), structured as: Qlearning.lua (the main module with the Q-learning implementation), circuit-learning.lua + circuit-learning.argos (Q-learning for path following), train-script.sh (runs the learning process for a given number of epochs), and circuit-testing.lua + circuit-testing.argos (to test the robot after training). The Q-table is stored as a csv file and updated at the end of each learning epoch; the first table is created by running create Q-table.lua with parameters Qtable-circuit.csv 256 5 — 256 states, 5 actions.

-- the heart of Q-learning (schematic, from Qlearning.lua)
Q[s][a] = (1 - alpha) * Q[s][a] +
          alpha * (reward + gamma * maxQ(next_state))

Suggested experiments with the code:

1. Before exploring the code, think of a possible implementation: how would you define states and actions? And the reward function?
2. Go back to step 1 until you are sure you know what to do if you had to program RL yourself.
3. Explore the code, starting from Qlearning.lua.
4. Assign values to the parameters of the algorithm (in circuit-learning.lua).
5. Run the learning code with batches of 10 or 20 epochs up to 50 (at least); at the end of each epoch test the behaviour. Apply a sound experimental evaluation: run the robot from different initial conditions and collect statistics using test-script.sh — the protocol of Chapter 15 applied to a learned controller.
6. Repeat the whole learning phase with different parameter values; try different combinations of train/test images.

Check your understanding