Reinforcement learning: from MDP to deep and multi-agent RL

1. From DTMC to MDP: actions and rewards

Deck 09 opens by situating reinforcement learning inside this course: "RL is a natural topic for this course, at this stage; technically, it is very related to modelling (DTMC) and simulation." The derivation is a staircase of three questions:

• what if we track actions (and rewards) in a DTMC? — MDP!
• what does it mean to optimise those actions? — MDP solution!
• what does it mean to seek optimisation by "experience"? — RL!

Recall the DTMC of chapter 10, section 3: a couple ⟨S, →⟩ where → ⊆ S × [0,1] × S — a directed graph whose edges carry probabilities, with two sanity conditions (deadlock or total probability 1; at most one arc between two states). The DTMC "describes the probabilistic evolution of a system" while abstracting away duration (a tick) and, crucially, the cause of non-determinism — which "can be due to observation of different outcomes of an unknown phenomenon", "the existence of an internal component taking decisions probabilistically", or "an external cause out of system's control".

To capture the cause, the DTMC is evolved in two steps. First: "add a notion of 'action' performed by an external entity (agent), whose outcome can be probabilistic" — a DTMC with actions, a triple ⟨S, A, →⟩ with → ⊆ S × A × [0,1] × S, whose sanity condition is per-action: for every state and action, either deadlock or outgoing probability 1. This "unveils non-determinism" into two components: "cause 1: non-determinism due to a 'trackable' decision (action); cause 2: non-determinism due to unknow effect of the decision (probability)". The whole system then "naturally splits in two parts": the environment — "the entity receiving the decision and accordingly 'change state' probabilistically" — and the agent — "the entity taking the decision". Note the deck's precision: "the automaton only models the environment response, actually".

Second: "add a notion of numerical reward, which the agent could use to decide". Rewards "are typically numerical values associated to each arrow of the automaton, whose cumulation the agent wants to maximise". The result is the Markov Decision Process:

MDP = ⟨S, A, R, →⟩   where   → ⊆ S × A × [0,1] × R × S      a,p,r
                                                     write S −−−→ S′

with the same sanity conditions per state-action pair (deadlock or probability 1, at most one arc labelled a from S to S′). "Essentially: DTMCs + rewarded actions."

2. The optimisation problem of MDPs

With rewards on the arrows, the natural question is: "what is the 'policy' that creates most cumulative reward?" A policy is "a selection of which action to take at each state". The deck's running example is a two-state automaton: from S1, the agent can send (with 99% probability reaching a success state with reward rs, and 1% reaching a failure state with reward rf) or wait (reward rw, staying). The problem: "given r_f, r_s, r_w, whether it is more convenient in S1 to send or just wait".

Two readings fix the reasoning. "Because of the markov property this cannot depend on the past (e.g. whether it is the first or second time we are taking the decision)" — the decision in S1 is the same every time. And the expected returns are computable by recursion: "e.g.: always waiting gives k·r_w after k choices; e.g.: sending has 99% probability to give r_s, and 1% to give r_f plus the reward we can get in k−1 choices, recursively". The widget below lets you play the trade-off; the point is that "MDPs are aimed at computing those estimates and corresponding policies" — the optimality problem of the MDP.

3. From MDP to RL: the learning problem

The step from MDP to RL is about knowledge. An MDP "allows one to compute how much reward a policy is expected to achieve, taking as input the probabilistic behaviour of the environment"; reinforcement learning is, technically, "the problem of learning what to do so as to maximize a numerical reward signal" — "learning means that the learner discovers (and tracks) by exploration the effect of actions, and recalls it for the future". RL "derives policies possibly starting with incomplete (or absent) knowledge about the behaviour of the environment and expected long-time reward of a state/action".

• model-based RL — the agent knows a model for the environment, "but this is typically too big (defaults to MDP)";
• model-free RL — the agent does not know the environment "and proceeds by trial-and-error".

RL is the third category of machine learning — "other than supervised/unsupervised learning" — with key features: "closed-loop, no pre-instructions, consequences of actions are in future". The scenario is "a learning agent interacting with the environment to achieve a goal: the agent senses the environment, takes actions, and has the goal of obtaining reward". The examples of the deck are worth keeping: learning to play chess or videogames; "an adaptive controller of an actuator that adjusts its parameters"; "a mobile robot deciding to go recharging or continue its task in next room"; "a drone learning not to crash into others"; "a device learning which neighbours to stop trusting" — the last one already smells of aggregate computing.

The agent-environment interface fixes the symbols: time is discrete steps t = 0, 1, 2, 3, ...; the agent receives a representation of the environment state St ∈ S and decides to execute an action At ∈ A(St); one time step later it receives a reward Rt+1 ∈ R and a state St+1. Agent decisions are framed as a policy πt that can be probabilistic: πt(a|s) is the probability to execute action a at state s. "Hence the MDP (state, actions, rewards) just models the environment."

The interface is "an element of design": steps "need not be fixed-length... just successive stages"; actions "can be low-level controls, or high-level decisions"; states "can be complete sensor readings, high-level descriptions, mere beliefs, intentions, or memory of past"; "the agent/environment boundary is flexible: what the agent can control is considered outside"; and "reward is typically considered as coming from outside the learner". The key modelling problem: "apply a proper abstraction such that the number of states and actions are reasonably limited to avoid state-explosion problems" and "the obtained policy is a good one for the problem at hand".

4. Rewards, returns and the discount rate

What is the objective? The reward hypothesis is "a key of RL": "all is meant by goals/purposes/success can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (reward)". The deck's examples show how flexible the encoding is: to learn to walk, "give rewards proportional to distance reached"; to escape quickly, "give −1 each time escape is not achieved"; to collect, "give +1 each time an item is collected"; "not to fall on holes, give −1000 each time it falls"; to win a board game, "give +1 on winning, −1 on losing, 0 in any other case".

Tasks split into two kinds: episodic — "if agent/environment interaction breaks in subsequences that restart in the same way" — and continuing — "if agent/environment interaction is long life". The return of an episode is the cumulative reward to be maximised: with an episode written as the sequence S0, A1, R1, S1, A2, R2, S2, ..., the return expected at time t is

G_t = Σ_{k=0}^{T} γ^k R_{t+k+1}        with  0 ≤ γ ≤ 1

The parameter γ is the discount rate: "it measures the relative value we give to future rewards. γ = 0 means the agent is myopic: it cares of present and does not value future. With episodic tasks, one could even choose γ = 1. With continuing tasks, γ < 1." (Without discounting, an infinite continuing task could accumulate infinite return — the reason γ < 1 keeps the sum finite.)

5. Formalising: dynamics, Markov property, value functions

The lecture now formalises the problem. Inputs: the structure of states and actions S, A; the environment dynamics (without the Markov hypothesis) Pr{Rt+1 = r, St+1 = s′ | S0, A0, R1, ..., St, At}; the initial state S0; the discount factor γ and episode length T. A policy π "gives a distribution over episodes"; each episode e has probability pe and return Ge = R1 + γR2 + γ²R3 + ... + γT−1RT; a policy's overall return is Ee[Ge] = Σe p(e)Ge. "RL: find the policy that probabilistically gives the highest return."

States should "summarise the past compactly, so that we never need to know past states — namely: the markov property". With it, the general dynamics collapses to p(s′, r|s, a) := Pr{Rt+1 = r, St+1 = s′ | St, At} — "from state s with action a move to s′ and receive reward r". From this single function everything is derived:

• expected reward of an action at a state: r(s, a) = E[Rt+1 | St=s, At=a] = Σr,s′ p(s′, r|s, a)·r;
• state-transition probability: p(s′|s, a) = Σr p(s′, r|s, a);
• expected reward at a state under a policy: rπ(s) = Σa π(a|s) r(s, a).

The collector robot example instantiates it: "state represents how much energy the robot has left"; rewards rwait, rsearch measure items collected while waiting/searching; "−3 stands for cost for retrieving an inactive robot and recharging"; α, β describe the energy cost of searching. "If used online, r_wait, r_search are observed; if used offline, they could hide a random variable over the collected items." The expected rewards: r(high, wait) = rwait, r(high, search) = rsearch[(1−α) + α] (the two outcomes of searching weighted by their probabilities), and for a purely non-deterministic policy rπ(high) = r(high, wait)/2 + r(high, search)/2.

To estimate long-term return, the lecture introduces the two value functions. Under policy π:

state-value:   v_π(s)  = E_π[ G_t | S_t = s ]  = E_π[ Σ_{k=0}^∞ γ^k R_{t+k+1} | S_t = s ]
action-value:  q_π(s,a) = E_π[ G_t | S_t = s, A_t = a ]

"One can easily be derived from the other", and both "can be: computed (exactly or with approximation), learnt from experience, e.g. by Monte-Carlo methods".

6. Bellman equations and the grid example

The Bellman equation is "the recursive definition of v_π (q_π is similar)":

v_π(s) = Σ_a π(a|s) Σ_{s′,r} p(s′, r|s, a) [ r + γ·v_π(s′) ]

Read as the deck does: "for each triple a, s′, r compute probability π(a|s)p(s′, r|s, a), weigh the quantity in brackets by this probability, and sum all possibilities". The value of a state is the expected immediate reward plus the discounted value of wherever you land — one equation per state.

The grid example fixes the intuition: a robot wandering a field, moving left-right-up-down, "reward typically 0; reward is −1 when trying to move out of area (but won't move); in two cases, moving everywhere causes a jump and exceptional reward", with γ = 0.9. Computing the state-value function for a purely non-deterministic policy "is a system of n equations in n variables, where n is cardinality of S (25 above)"; "existence of unique solution is guaranteed, but it is costly to compute". The TryQMatrix facade of section 9 uses exactly this 5×5 grid with rewards +10 at (1,0) and +5 at (3,0), jumps to (1,4) and (3,2), γ = 0.9.

Optimality: "a policy is better than another (π ≥ π′) if its expected value is ≥ in all states"; "greater v (or q) induces better π"; "optimal policies π* are such that v*(s) = max_π v_π(s) and q*(s, a) = max_π q_π(s, a)". The Bellman optimality equation — replace the policy average by the max — "is a system of N non-linear equations and N unknowns... it provably has a unique solution". Once v* is known, "π is easily found by greedy action selection: namely, deterministically going to the directions increasing v*"; "knowing q* below makes policy identification even easier". The greedy policy is the optimal one: "always choose the action that produces immediate highest return (v* or q*); if there are two such actions, it could possibly be non-deterministic".

The honest caveat of the lecture: "unfortunately, computing q* or v* quickly becomes untractable (in space and time); they should be approximated, or computed partially (by exploring subparts of s, a); additionally p is not always fully known — or even not existing, due to non-markov environments." This is the door to learning (section 7).

7. Learning policies: dynamic programming, Monte Carlo, temporal differences

The lecture surveys the three families of solution techniques, ordered by how much of the model they need:

• Dynamic Programming (DP) — model-based: "solving a decision problem by breaking it in a sequence of decision steps (each considered as byproduct of some local learning); namely, start from v₀, and iteratively evolve it (v₁, v₂, v₃, ...) until stabilisation to optimum". The iteration is ∀s: vk+1(s) = maxa Σs′,r p(s′, r|s, a)[r + γvk(s′)]; "by the Bellman theorem, transition from v_k to v_k+1 is an improvement, hence there's convergence". "Can give good results in time, but is still impractical with many states." The deck notes updates can be asynchronous — "somehow making it resemble a stabilising 'field computation' over v, as in 'Bellman gradients'" — a first echo of chapter 14.
• Monte Carlo (MC) methods — model-free: "solving a decision problem without knowing the environment (p), hence solely based on experience on probing the environment (hence working with many samples)". "Can nicely fit simulation scenarios, where the environment is a complex computational system" — the Alchemist scenarios of chapter 12. MC with exploring start: start from arbitrary π and q; choose S₀ and A₀ (all pairs with non-zero probability); generate an episode following π; for each (s, a) in the episode extract rewards and update q(s, a), e.g. as a weighted average αqold + (1−α)qnew. MC without exploring start: stick to an initial state but "be sure that all states will eventually be traversed: π should never give less than ε > 0 probability to any available action" — e.g. super-impose a non-deterministic policy giving ε to all actions.
• Temporal Difference (TD) methods — "a combination of DP and MC": "like MC it learns from raw experience (generated/sampled episodes); like DP it locally updates estimates based on other learned estimates, without the need of generating full episodes". The family includes TD(0) prediction (evolves V from a finite number of episodes), Q-learning ("updates q using next state and greedy action for current q — off-policy"), SARSA ("updates q using next state and action given by current policy — on-policy"), n-step prediction, TD(n). "Often need to combine elements of the above techniques."

8. Q-learning

Q-learning is the algorithm the course actually implements. Its update is one line:

Q(S_t, A_t) := (1 − α)·Q(S_t, A_t) + α·[ R_{t+1} + γ·max_a Q(S_{t+1}, a) ]

The procedure: "initialize Q arbitrarily, and put 0 on terminal state; for each episode, starting from a Q₀: 1. choose A from S using a policy from Q that is explorative (e.g. ε-greedy); 2. take action A and observe R, S′ (the simulated/actual step is here!); 3. update Q; 4. S := S′; 5. end episode when S is terminal". The design space: "define your environment interface: S, A (properly abstract!); define your environment dynamics: S, A → S′, R (MDP, or external 'oracle'); define q-learning parameters: Q₀, α, γ, π^ε_Q".

Note the "simulated/actual step is here!": Q-learning does not care where the experience comes from — an MDP model, a simulator like Alchemist, or the real world. That is what makes it the bridge between this chapter and chapter 12.

Methodologically, the deck separates two uses, and their combination:

• Offline ("adding some offline learning feature to a system"): frame the problem as an RL one; create a simulation scenario (with realistic traces and proper rewards); simulate and learn a Q-function (typically a table); in production, use the derived π for the deciding agent.
• Online ("adding some online learning feature"): frame the problem; implement the agent as a q-based policy selector; in production run the system and have the agent "slowly" learning — possibly "initially just observe, and later make decisions effective".

9. Q-learning in Scala: the QRL toolkit

The lecture develops a small Scala prototype — "possible with simple algorithms, like q-learning; gives much more confidence on the inner mechanisms; allows more informative explorations; will allow to combine with other owned technologies (scafi, that is)". The structure: model.QRL — "a family trait with definitions and template methods" (Environment, Policy, System, VFunction, Q, LearningProcess); model.QRLImpl — "a family trait with objects and case classes, providing implementations"; examples.TryQMatrix — "a facade to play with grid-like examples".

Read the first part of the API: an Environment is just a function from (state, action) to (reward, state); an MDP implements it by drawing from a weighted list of transitions — the "simulated/actual step" abstraction of section 8; a System wraps the environment with an initial state, a terminal predicate and a run producing a lazy list of (action, state) pairs.

trait QRL:
  type State
  type Action
  type Reward = Double
  type Probability = Double

  given random: scala.util.Random = new scala.util.Random()

  trait Environment extends ((State, Action) => (Reward, State))

  trait MDP extends Environment:
    def transitions(s: State): Set[(Action, Probability, Reward, State)]
    override def apply(s: State, a: Action): (Reward, State) =
      draw(cumulative(transitions(s).collect {
        case (`a`, p, r, s) => (p, (r, s))
      }.toList))

  type Policy = State => Action

  trait System:
    def environment: Environment
    def initial: State
    def terminal: State => Boolean
    def run(p: Policy): LazyList[(Action, State)]

Then the Q-function and the learning process. Q is an updatable table: bestPolicy is the greedy actions.maxBy(this(s, _)); epsPolicy draws a uniform action with probability ε; vFunction is the state value max over actions — the bridge between the table and the value functions of section 5:

trait Q extends ((State, Action) => Reward):
  def actions: Set[Action]
  def update(s: State, a: Action, v: Reward): Q
  def bestPolicy: Policy = s => actions.maxBy(this(s, _))
  def epsPolicy(f: Probability): Policy = _ match
    case _ if Stochastics.drawFiltered(_ < f) => Stochastics.uniformDraw(actions)
    case s => bestPolicy(s)
  def vFunction: State => Reward = s => actions.map(this(s, _)).max

trait LearningProcess:
  def system: System
  def gamma: Double
  def alpha: Double
  def epsilon: Double
  def q0: Q
  def updateQ(s: State, qf: Q): (State, Q)
  def learn(episodes: Int, episodeLength: Int, qf: Q): Q

The implementation is the deck's own QRLImpl.QLearning — the update of section 8 transcribed line by line, with a tail-recursive episode runner:

case class QLearning(
    override val system: QSystem,
    override val gamma: Double,
    override val alpha: Double,
    override val epsilon: Double,
    override val q0: Q) extends LearningProcess:

  override def updateQ(s: State, qf: Q): (State, Q) =
    val a = qf.epsPolicy(epsilon)(s)
    val (r, s2) = system.environment(s, a)
    val vr = (1 - alpha) * qf(s, a) + alpha * (r + gamma * qf.vFunction(s2))
    val qf2 = qf.update(s, a, vr)
    (s2, qf2)

  @tailrec
  final override def learn(episodes: Int, length: Int, qf: Q): Q =
    @tailrec
    def runSingleEpisode(in: (State, Q), episodeLength: Int): (State, Q) =
      if episodeLength == 0 || system.terminal(in._1) then in
      else runSingleEpisode(updateQ(in._1, in._2), episodeLength - 1)
    episodes match
      case 0 => qf
      case e => learn(e - 1, length, runSingleEpisode((system.initial, qf), length)._2)

The facade wires the grid example — the one of section 6 — with rewards and jumps as partial functions, and prints the v-function and the greedy policy after learning:

object TryQMatrix extends App:
  import u09.model.QMatrix.Move.*
  import u09.model.QMatrix.*

  val rl: QMatrix.Facade = Facade(
    width = 5, height = 5,
    initial = (0, 0),
    terminal = { case _ => false },
    reward = { case ((1, 0), _) => 10; case ((3, 0), _) => 5; case _ => 0 },
    jumps = { case ((1, 0), _) => (1, 4); case ((3, 0), _) => (3, 2) },
    gamma = 0.9, alpha = 0.5, epsilon = 0.3, v0 = 1)

  val q0 = rl.qFunction
  println(rl.show(q0.vFunction, "%2.2f"))
  val q1 = rl.makeLearningInstance().learn(10000, 100, q0)
  println(rl.show(q1.vFunction, "%2.2f"))
  println(rl.show(s => q1.bestPolicy(s).toString, "%7s"))

The deck's results — the v-table printed by learn(10000, 100, q0) — and the parameter lesson:

22.0  24.4  22.0  19.4  17.5
19.8  22.0  19.8  17.8  16.0
17.8  19.8  17.8  16.0  14.4
16.0  17.8  16.0  14.4  13.0
14.4  16.0  14.4  13.0  11.7

> < < < <
> ^ < < <
> ^ < < <
> ^ < < <
> ^ < < <

parameters: exploration is key here — ε = 0.3, α = 0.5, γ = 0.9
it creates the optimal policy rather quickly (in 50 episodes of length 50)
optimal v-table requires much more episodes

10. Deep Q-learning: from tables to neural networks

The advanced deck (Aguzzi, "Advanced Topics in Reinforcement Learning") starts from the three walls that tabular RL hits: large state spaces ("the number of states grows combinatorially with the problem size"; "memory issue: we cannot explicitly store all states and their values; data issue: many states are rarely or never visited during training; learning issue: no chance to generalize if each state is treated as an isolated entry in a table"), continuous action spaces ("no enumeration: we cannot compute and compare a value for every possible action; no argmax by search: selecting the best action is now an optimization problem"), and generalisation ("ability to perform well on unseen states, tasks, or environments... memorizing trajectories or opponent behaviors is not enough"). The numbers of the deck make it visceral: Go has ~10¹⁷⁰ possible states against ~10⁸⁰ atoms in the universe; chess has ~10⁴⁴ states, "total space required ∼ 10³⁴ terabytes".

Deep Reinforcement Learning (DRL) is "the use of deep neural networks to approximate the value function / policy", with three key features matching the three walls: "value function approximation (instead of tables) — handle large state space; policy gradient (instead of Q-Learning) — handle continuous action space; deep neural networks — handle generalization (representation learning)". The value-based vs policy-based split: value-based algorithms "learn a value function, typically V(s) or Q(s,a); the policy is obtained indirectly by choosing the action with the highest estimated value: a* = arg max_a Q(s, a)" — great for discrete actions, does not transfer to continuous actions; policy-based algorithms "learn directly a parametrized policy π(a|s)... typically through policy-gradient methods" (REINFORCE, PPO) — "the method optimizes the decision rule itself, rather than estimating values first and extracting a policy afterwards".

Deep Q-Learning is "Q-Learning, but the Q-table is replaced by a neural approximator": Q(s, a, θ) ≈ Q*(s, a). The naive version is unstable, for two reasons:

• correlation — "consecutive transitions are temporally correlated, so minibatches are not i.i.d.";
• moving target — "both target and prediction depend on the same changing parameters θ" (the regression view: L(θ) = E[(ynaive − Q(s,a,θ))²] with ynaive = r + γ maxa′ Q(s′, a′, θ)).

The two stabilisations are the heart of DQN (Mnih et al., 2013):

• Replay buffer — "store the transitions (s, a, r, s′) in a replay buffer D; during training, sample a random minibatch of past transitions from D". It breaks temporal correlation, makes minibatches closer to the i.i.d. assumption of SGD, and reuses past experience ("improving sample efficiency").
• Fixed target network — "use a separate network to compute the target value; the target network is updated every C steps": for a sampled transition compute y = r + γ maxa′ Q(s′, a′, θ−) with the frozen θ−, train the online network on L(θ) = E[(y − Q(s,a,θ))²], and every C steps copy θ− ← θ. "The target is fixed for C steps, so the prediction network is no longer chasing a target that moves at every update."

Exploration uses ε-greedy with decay: the behaviour policy (with probability ε a random action, otherwise greedy w.r.t. Q(s,a,θ)) is decoupled from the target policy ("the update still pushes the network toward the greedy policy induced by Q"); "high ε early on broadens state-action coverage while the Q-function is still inaccurate; then ε is reduced, often down to a small floor ε_min, to shift from exploration to exploitation". This works precisely because "DQN is off-policy: it can learn from replayed transitions collected with older behaviour policies and different ε values".

The algorithm: (1) initialize the replay buffer D, the online parameters θ, copy θ⁻ ← θ; (2) for each step, observe s_t, select a_t with the ε-greedy behaviour policy, execute, observe r_t and s_t+1, store (s_t, a_t, r_t, s_t+1) in D; (3) sample a minibatch, set y_i = r_i if s′_i is terminal else ri + γ maxa′ Q(s′i, a′, θ−), update θ by minimising (y_i − Q(s_i, a_i, θ))², and every C steps copy θ⁻ ← θ. Limits: "works only for discrete action spaces; sample inefficiencies". Extensions: Double DQN ("reduce overestimation bias by decoupling action selection and action evaluation in the target"), Prioritized Experience Replay ("sample the transitions from the replay buffer according to their TD-error"), Rainbow DQN ("combine several DQN improvements in a single agent").

The working example is CartPole: state st = (xt, ẋt, θt, θ̇t) — cart position, cart velocity, pole angle, angular velocity; actions: push left or right; reward 1 if the episode continues, 0 if it terminates — "maximizing return means surviving for many consecutive steps". The companion codebase (advanced-reinforcement-learning-asmd-code) shows the whole pipeline in Scala: the Agent/Learner abstractions (with the key distinction between behavioural and optimal policy — the ε-greedy split in code), the ReplayBuffer storing exactly the (s, a, r, s′, done) tuples, the DQN as "a compact MLP that outputs one Q-value per discrete action", and DeepQAgent with its two explicit networks, the terminal mask zeroing the future term, and the scheduler deciding when to sync the target network.

11. Multi-agent reinforcement learning

Multi-Agent Reinforcement Learning (MARL) is the extension of the chapter to many learners: "multiple agents learn to take the right actions (policy) to maximise a reward signal", with applications from videogames and traffic control to swarm robotics, trading, energy management and environmental monitoring. The step of abstraction: "from MDPs to stochastic games".

The stochastic game (a.k.a. Markov game) is the common fully-observable model:

S = ⟨N, S, {A_i}_{i∈N}, P, {R_i}_{i∈N}, ρ₀⟩   with N = {1, ..., N}
S: global environment state · A_i: action space of agent i, joint action A = A₁ × ... × A_N
P(s′ | s, a): transition model · R_i(s, a, s′): reward of agent i · ρ₀: initial-state distribution

The repeated Rock–Paper–Scissors example fixes the reading: N = 2, both action spaces {Rock, Paper, Scissor}, "state tracks the last joint action: S ⊂ (A₁ ∪ {⊥}) × (A₂ ∪ {⊥})", deterministic transitions; the payoff matrix is the classic zero-sum one (Rock vs Paper: −1, +1, etc.). One step of evolution: at time t the environment is in s_t; the agents choose the joint action a_t = (a¹_t, ..., a^N_t); the environment samples s_t+1 ∼ P(·|s_t, a_t); each agent receives rⁱ_t+1 = Rⁱ(s_t, a_t, s_t+1). The model is "idealised": "in many MARL problems agent i only sees a local observation oⁱ_t", so it is "mainly a conceptual tool for understanding interaction". Common refinements: POSG (partially observable stochastic games), Dec-POMDP (cooperative partial observability), extensive-form games, mean-field games (large populations).

How to read a MARL task — the deck's four questions: "Are rewards aligned? (cooperative vs competitive); Who acts and who learns? (decentralized vs centralized); Are the agents symmetric? (homogeneous vs heterogeneous); Is coordination only implicit? (environment dynamics vs communication)." Changing any dimension changes the algorithm class. "Rock–Paper–Scissors is competitive: same actions, opposite incentives. The next alignment task is cooperative: shared reward, coordination challenge."

The case study is align the agents (in the codebase, BoundedWorld): "several agents move on the same grid with local actions: up, down, left, right, or stay; the team objective is simple: end up on the same row. The reward is shared by all agents: if they are aligned, everyone gets 0; otherwise, everyone gets −1" (r¹ = ... = r^N = −1 vs r¹ = ... = r^N = 0). The implementation details matter: each agent sees a relative state RelativeState(rowDiff, colDiff) — "the agent does not need the whole grid configuration: it only needs a local description of where the others are with respect to itself. This creates symmetry: the agents are homogeneous, execution is naturally decentralised, and later parameter sharing becomes plausible."

The lecture then compares three ways to learn the same task:

• Independent learners — each agent keeps its own Q-table over the relative state. "This is the easiest way to reuse single-agent RL in a multi-agent setting. Main issue: from the viewpoint of one learner, the environment is non-stationary because the other agents are learning and changing policy at the same time."
• Central controller — one learner sees the full state and chooses the whole joint action. "Coordination is easier because it is encoded directly in the action selection. Why it becomes brutal here: with boundSize = 10 and numAgents = 6, the absolute state space is about 10¹²; the joint action space is 5⁶ = 15625. Centralization helps with coordination, but it explodes the tabular learning problem."
• Parameter sharing — "the agents still execute actions locally, but they all update the same learning object. This works because the task is symmetric: same action space, same reward structure, same relative-state representation. This is often the sweet spot in cooperative homogeneous settings: decentralised execution without the combinatorial cost of learning joint actions explicitly."

What richer settings may require: "communication: agents exchange messages, not only actions; CTDE: centralized training with decentralized execution; heterogeneity: different roles, action spaces, or policy classes; function approximation: the repo's sharedDeepQLearner() keeps the same sharing idea with a neural approximator".

12. Lab: operational steps and R&D directions

The lab deck (09-Lab) condenses the whole chapter into one slide: "MDP is essentially DTMC plus actions/rewards, and the goal of maximising cumulative reward; optimal policy can be found by Bellman equations, which badly scale in practice — large state-space is addressable by Dynamic Programming (iterative algorithms); unknown model or non-Markovianity is addressable by Monte Carlo approaches (simulation). Q-learning: mixed DP and MC, with an off-policy learning that keeps improving the Q-table; Deep Q-learning: represents Q-table by a DNN, with additional ingredients to properly converge; MARL: many agents call for a wider model and specific algorithms."

Operational steps

• Step 1 — the RL repo and Q-learning. Download asmd-public-models (the course repo); import it in IntelliJ as an SBT project; look at scala/u09/examples; run TryQLearningMatrix ("it should produce the expected matrix with directions"); check how variations of key parameters (ε, γ, α, episode length) affect learning; check how learning gets more difficult as the grid size increases.
• Step 2 — the DQN and MARL repo. Download advanced-reinforcement-learning-asmd-code; import it as an SBT project; look at scala/it/unibo/gym for Deep Q-Learning (the CartPole of section 10); look at scala/it/unibo/examples for MARL (the BoundedWorld alignment task of section 11).

R&D tasks

Test your knowledge