Reinforcement learning

7.1 Markov decision process

What RL is designed to “solve”. An MDP is given by \((\mathcal{S},\mathcal{A},P,R,\gamma)\)

1. State space \(\displaystyle \mathcal S\)

   All the possible configurations the environment can be in. At time \(t\) the env “is” in some state \(s_t\in\mathcal S\).

2. Action space \(\displaystyle \mathcal A\)

   All the moves or controls the agent can choose. Agent picks \(a_t\in\mathcal A\) when in state \(s_t\).

3. Transition dynamics \(\displaystyle P\bigl(s_{t+1}\mid s_t,a_t\bigr)\)

   A (possibly stochastic) rule for how the world updates when you take action \(a_t\) in \(s_t\). E.g. in CartPole, push left/right → new pole‑angle and cart‑position.

   For the purposes of describing the problem we write this out, but in fact if we are bothering with RL we do not actually know this. All we do is sample from it. E.g. in CartPole, you don’t predict the next angle of the pole, but you can sample it by running the simulation.

   I mean, you can predict it in CartPole, but you are not required to, and totally black box systems are amenable to RL.

4. Reward function \(\displaystyle R\bigl(s_t,a_t,s_{t+1}\bigr)\)

   The scalar “feedback” we get when you go from \(s_t\) to \(s_{t+1}\) via \(a_t\). High reward = good; low (or negative) = bad.

   Once again, we do not know this function, we just sample from it after taking an action. E.g. in CartPole, you get a reward of +1 for every time step you keep the pole upright.

5. Discount factor \(\displaystyle \gamma\in[0,1]\)

   How much we prefer “now” rewards over “later” rewards where \(\gamma=0\) → we only care about immediate reward; \(\gamma\to1\) → we care a lot about the future.

6. Initial state distribution \(\displaystyle \rho_0(s)\)

   Where episodes start: you sample \(s_0\sim\rho_0\). Often a fixed start state or a uniform/random choice.

   People often seem to suppress this in the problem; I don’t think it adds much complexity in practice.

7. Horizon \(T\) (or termination condition)

   Max length of an episode (or “done” flag). If infinite, we rely on \(\gamma<1\) to keep returns finite. This is often suppressed also.

The next few are definitions that we find convenient to make, dependent upon the above.

8. Policy \(\displaystyle \pi_\theta(a\mid s)\)

   Our agent’s “strategy”: a mapping from state→distribution over actions. Parameterized by \(\theta\) (e.g. the weights of a neural net).

9. Trajectory \(\displaystyle \tau = (s_0,a_0,r_0,\dots,s_{T})\)

   One full run‑through of states, actions, and rewards until done.

10. Return \(\displaystyle G_t=\sum_{k=t}^{T-1}\gamma^{\,k-t}\,r_k\)

    The total (discounted) sum of rewards from time \(t\) onward — What we’re trying to maximise on average.

11. Objective \[ J(\theta) = \mathbb{E}_{\tau\sim\pi_\theta}\bigl[G_0\bigr] = \mathbb{E}\Bigl[\sum_{t=0}^{T-1}\gamma^t\,r_t\Bigr]. \]

We aim to pick \(\theta\) to make expected return as large as possible.

Now if we knew \(P\) and \(R\) and their forms were tractable, we could just use dynamic programming to solve the MDP; let us assume we do not know them.

9.1 Bootstrapping and the Temporal Difference update

When we actually take \(a_t\) in \(s_t\) and see \((r_t, s_{t+1})\), we can form a “one-step bootstrap” target — basically our best guess at what the true value should be: \[ r_t + \gamma \max_{a'} Q(s_{t+1},a'). \] Compare that to what we thought before, \(Q(s_t,a_t)\). The difference between them is the temporal-difference (TD) error: \[ \delta_t = r_t + \gamma \max_{a'} Q(s_{t+1},a') - Q(s_t,a_t). \] Then we nudge our estimate in the right direction: \[ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha,\delta_t. \] Here, \(\alpha\) is the learning rate — how fast we update — and \(\gamma\) is the usual discount factor for future rewards.

9.2 Exploration

If we just keep picking the current best-looking action, we get stuck fast — often with a overconfident bad choice. So we mix in some randomness.

The simplest hack is ε-greedy:

• With probability \(\epsilon\), pick a random action (“explore”).
• With probability \(1 - \epsilon\), pick the action with the highest \(Q(s,a)\) (“exploit”).

Usually \(\epsilon\) starts high and decays over time — curious early, confident later.

I find ε-greedy ugly but it works and it’s easy to code. There are more elegant exploration schemes — Bayesian ones, for instance — which show up again in bandit problems.

LLM-generated conversion of that word salad into PyTorch:

import torch
import torch.nn as nn
import torch.optim as optim
import random

class QNetwork(nn.Module):
    def __init__(self, state_dim, action_dim, hidden=128):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, hidden),
            nn.ReLU(),
            nn.Linear(hidden, hidden),
            nn.ReLU(),
            nn.Linear(hidden, action_dim)
        )
    def forward(self, state):
        # state: torch.Tensor of shape [batch, state_dim]
        return self.net(state)  # returns [batch, action_dim]

def select_action(q_net, state, eps, device):
    """
    ε‑greedy selection
    state: numpy array or list → torch.Tensor [1, state_dim]
    returns: action (int)
    """
    if random.random() < eps:
        return random.randrange(q_net.net[-1].out_features)
    state_v = torch.tensor([state], dtype=torch.float32, device=device)
    with torch.no_grad():
        q_vals = q_net(state_v)  # [1, A]
    return int(q_vals.argmax(dim=1).item())

def train_qlearning(
    env,
    q_net,
    optimizer,
    num_episodes,
    gamma=0.99,
    eps_start=1.0,
    eps_end=0.01,
    eps_decay=0.995,
    device="cpu"
):
    eps = eps_start
    for ep in range(1, num_episodes + 1):
        state = env.reset()
        done = False
        total_reward = 0.0

        while not done:
            # 1) Pick action
            a = select_action(q_net, state, eps, device)

            # 2) Step environment
            next_state, r, done, _ = env.step(a)
            total_reward += r

            # 3) Compute TD target
            state_v      = torch.tensor([state],      dtype=torch.float32, device=device)
            next_state_v = torch.tensor([next_state], dtype=torch.float32, device=device)
            q_vals       = q_net(state_v)            # [1, A]
            next_q_vals  = q_net(next_state_v)       # [1, A]
            q_sa         = q_vals[0, a]
            target       = r + (0.0 if done else gamma * next_q_vals.max().item())

            # 4) Compute loss & backprop
            loss = (q_sa - target) ** 2
            optimizer.zero_grad()
            loss.backward()
            optimizer.step()

            # 5) Move on
            state = next_state

        # 6) Decay epsilon
        eps = max(eps_end, eps * eps_decay)

        # Logging
        if ep % 10 == 0:
            print(f"Episode {ep:4d} | Return: {total_reward:.2f} | ε={eps:.3f}")

# Example usage:
import gym

env       = gym.make("CartPole-v1")
device    = torch.device("cuda" if torch.cuda.is_available() else "cpu")
q_net     = QNetwork(state_dim=env.observation_space.shape[0],
                     action_dim=env.action_space.n).to(device)
optimizer = optim.Adam(q_net.parameters(), lr=1e-3)

train_qlearning(env, q_net, optimizer, num_episodes=500)

9.3 Actor-critic

TBC

9.4 Regularization: PPO

TBC

9.5 Model-based RL

TBC