Overview of Reinforcement Learning (Optional Material)

Reinforcement Learning has been used in various applications such as robotics, game playing, recommendation systems, and more. Reinforcement Learning (RL) is a broad topic and we will only cover basic aspects of RL.

No external libraries are required for this chapter, we implement Q-learning from scratch in TypeScript.

The examples for this chapter are in the directory source-code/reinforcement_learning.

Architecture diagram for Q-Learning on FrozenLake and MDP Value Iteration
Figure 8. Architecture diagram for Q-Learning on FrozenLake and MDP Value Iteration

Overview

Reinforcement Learning is a type of machine learning that is concerned with decision-making in dynamic and uncertain environments. RL uses the concept of an agent which interacts with its environment by taking actions and receiving feedback in the form of rewards or penalties. The goal of the agent is to learn a policy which is a mapping from states of the environment to actions with the goal of maximizing the expected cumulative reward over time.

There are several key components to RL:

  • Environment: the system or “world” that the agent interacts with.
  • Agent: the decision-maker that chooses actions based on its current state, the current environment, and its policy.
  • State: a representation of the current environment, the parameters and trained policy of the agent, and possibly the visible actions of other agents in the environment.
  • Action: a decision taken by the agent.
  • Reward: a scalar value that the agent receives as feedback for its actions.

Reinforcement learning algorithms can be divided into two main categories: value-based and policy-based. In value-based RL the agent learns an estimate of the value of different states or state-action pairs which are then used to determine the optimal policy. In contrast, in policy-based RL the agent directly learns a policy without estimating the value of states or state-action pairs.

If you enjoy the overview material in this chapter I recommend that you consider investing the time in the Coursera RL specialization https://www.coursera.org/learn/fundamentals-of-reinforcement-learning taught by Martha and Adam White.

My favorite RL book is “Reinforcement Learning: An Introduction, second edition” by Richard Sutton and Andrew Barto, that can be read online for free at http://www.incompleteideas.net/book/the-book-2nd.html.

An Introduction to Markov Decision Process

Before we can write a reinforcement learning agent, we need to understand the mathematical framework that RL is built upon: the Markov Decision Process (MDP). An MDP provides a formal way to model sequential decision-making problems where outcomes are partly random and partly under the control of a decision-maker.

Let’s start by defining the key terms:

  • Sequential decision problem: a problem where decisions are made in sequence over time, and each decision affects future states and rewards.
  • Fully observable: the agent can see the complete state of the environment at each step.
  • Stochastic environment: transitions between states are not deterministic.
  • Markov property: the future depends only on the current state and action, not on the history.
  • Bellman equation: Code Test where Code Test (gamma) is the discount factor.

The discount factor Code Test (between 0 and 1) controls how much the agent values future rewards versus immediate rewards.

Solving MDPs: Value Iteration in TypeScript

We implement value iteration for a simple 3×3 grid world:

 1 // mdp_demo.ts - Markov Decision Process with Value Iteration
 2 
 3 function valueIteration(
 4   nS: number, nA: number,
 5   P: number[][][], R: number[][],
 6   gamma = 0.9, threshold = 1e-6,
 7 ) {
 8   let V = new Array(nS).fill(0), policy = new Array(nS).fill(0), iterations = 0;
 9   while (true) {
10     iterations++;
11     const newV = new Array(nS).fill(0);
12     let maxDelta = 0;
13     for (let s = 0; s < nS; s++) {
14       let bestVal = -Infinity, bestA = 0;
15       for (let a = 0; a < nA; a++) {
16         let val = R[s][a];
17         for (let sp = 0; sp < nS; sp++) val += gamma * P[a][s][sp] * V[sp];
18         if (val > bestVal) { bestVal = val; bestA = a; }
19       }
20       newV[s] = bestVal; policy[s] = bestA;
21       maxDelta = Math.max(maxDelta, Math.abs(newV[s] - V[s]));
22     }
23     V = newV;
24     if (maxDelta < threshold) break;
25   }
26   return { policy, V, iterations };
27 }
28 
29 // --- 3×3 Grid World ---
30 const [nS, nA] = [9, 4];
31 const P = Array.from({ length: nA }, () => Array.from({ length: nS }, () => new Array(nS).fill(0)));
32 const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
33 
34 for (let s = 0; s < nS; s++) {
35   const [r, c] = [Math.floor(s / 3), s % 3];
36   for (let a = 0; a < nA; a++) {
37     const nr = r + dirs[a][0], nc = c + dirs[a][1];
38     P[a][s][(nr >= 0 && nr < 3 && nc >= 0 && nc < 3) ? nr * 3 + nc : s] = 1;
39   }
40 }
41 
42 const R = Array.from({ length: nS }, () => new Array(nA).fill(0));
43 for (let a = 0; a < nA; a++) { R[8][a] = 10; R[5][a] = -5; }
44 
45 const { policy, V, iterations } = valueIteration(nS, nA, P, R, 0.9);
46 const arrows = ["↑", "→", "↓", "←"];
47 
48 console.log("=== Custom 3×3 Grid World ===\nOptimal policy:");
49 for (let r = 0; r < 3; r++)
50   console.log(Array.from({ length: 3 }, (_, c) => `  ${arrows[policy[r * 3 + c]]}  `).join(""));
51 console.log(`\nValue function: [${V.map(v => v.toFixed(2)).join(", ")}]`);
52 console.log(`Iterations: ${iterations}`);

A Concrete Example: Q-Learning

When the transition and reward models are unknown, the agent must learn through trial and error. Q-learning is one of the simplest and most widely used model-free RL algorithms.

The Q-learning update rule is:

math

We implement a FrozenLake-style environment and Q-learning agent entirely in TypeScript:

 1 // frozen_lake_qlearning.ts - Q-Learning on FrozenLake from scratch
 2 
 3 class FrozenLake {
 4   private state = 0;
 5   private map = ["S","F","F","F", "F","H","F","H", "F","F","F","H", "H","F","F","G"];
 6   nStates = 16; nActions = 4;
 7 
 8   constructor(private slippery = true) {}
 9   reset() { return this.state = 0; }
10 
11   step(action: number) {
12     let a = action;
13     if (this.slippery && Math.random() < 0.667) a = (action + (Math.random() < 0.5 ? -1 : 1) + 4) % 4;
14     const [r, c] = [Math.floor(this.state / 4), this.state % 4];
15     const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
16     const nr = Math.max(0, Math.min(3, r + dirs[a][0]));
17     const nc = Math.max(0, Math.min(3, c + dirs[a][1]));
18     this.state = nr * 4 + nc;
19     const cell = this.map[this.state];
20     return { nextState: this.state, reward: cell === "G" ? 1.0 : 0.0, done: cell === "H" || cell === "G" };
21   }
22 }
23 
24 function evaluate(env: FrozenLake, Q: number[][], episodes = 100) {
25   let wins = 0;
26   for (let i = 0; i < episodes; i++) {
27     let s = env.reset(), done = false, steps = 0;
28     while (!done && steps++ < 100) {
29       const a = Q[s].indexOf(Math.max(...Q[s]));
30       const r = env.step(a);
31       s = r.nextState; done = r.done;
32       if (done && r.reward === 1) wins++;
33     }
34   }
35   return wins / episodes;
36 }
37 
38 function qLearning(env: FrozenLake, episodes = 10000, alpha = 0.1, gamma = 0.99, eps = 1.0, decay = 0.999, minEps = 0.01) {
39   const Q = Array.from({ length: env.nStates }, () => new Array(env.nActions).fill(0));
40   for (let ep = 0; ep < episodes; ep++) {
41     let s = env.reset(), done = false, steps = 0;
42     while (!done && steps++ < 100) {
43       const a = Math.random() < eps ? Math.floor(Math.random() * env.nActions) : Q[s].indexOf(Math.max(...Q[s]));
44       const { nextState, reward, done: d } = env.step(a);
45       done = d;
46       Q[s][a] += alpha * (reward + gamma * Math.max(...Q[nextState]) - Q[s][a]);
47       s = nextState;
48     }
49     eps = Math.max(minEps, eps * decay);
50     if ((ep + 1) % 1000 === 0) console.log(`  Episode ${String(ep + 1).padStart(5)}: success = ${evaluate(env, Q).toFixed(2)}`);
51   }
52   return Q;
53 }
54 
55 const env = new FrozenLake(true);
56 console.log(`=== Q-Learning on FrozenLake ===\nStates: ${env.nStates}, Actions: ${env.nActions}\n\nTraining:`);
57 const Q = qLearning(env);
58 
59 const arrows = ["↑", "→", "↓", "←"];
60 console.log("\nLearned policy:");
61 for (let r = 0; r < 4; r++)
62   console.log("  " + Array.from({ length: 4 }, (_, c) => arrows[Q[r * 4 + c].indexOf(Math.max(...Q[r * 4 + c]))]).join(""));
63 
64 const finalRate = evaluate(env, Q, 1000);
65 console.log(`\nFinal success rate (1000 episodes): ${finalRate.toFixed(2)}`);

The qLearning function implements the core algorithm. The epsilon-greedy strategy decays from 1.0 (pure exploration) to 0.01 over time.

When learning RL, start with tabular methods (Q-learning on discrete environments) before moving to deep RL. The concepts transfer directly, but debugging is far easier when you can inspect every Q-value in a table.

Reinforcement Learning Wrap-up

In this chapter we covered:

  • Markov Decision Processes: the mathematical foundation of RL, including states, actions, rewards, transition probabilities, the Bellman equation, and discount factors.
  • Value Iteration: computing optimal policies for known MDPs.
  • Q-learning: a model-free algorithm that learns from experience without needing transition probabilities, implemented from scratch in TypeScript.
  • Exploration vs exploitation: controlled by the epsilon-greedy strategy with decaying epsilon.

If this chapter sparked your interest, I encourage you to work through the Coursera specialization by Martha and Adam White and the Sutton/Barto book.

I tagged this chapter as optional material because I believe most readers will get more immediate value from mastering deep learning and pre-trained models. But if you find yourself working on sequential decision-making problems, robotics, game AI, resource allocation, dynamic pricing, the RL toolkit becomes indispensable.

Optional Practice Problems

To solidify your understanding of Markov Decision Processes (MDPs) and Q-learning, try implementing the following exercises using the code files in source-code/reinforcement_learning:

  1. Investigating Environment Stochasticity (FrozenLake) In frozen_lake_qlearning.ts, the FrozenLake class has a slippery parameter (default true) that introduces randomness in action execution.

    • Modify the training script to run with slippery = false.
    • Compare the number of training episodes needed to reach a stable success rate of 1.0 vs. the slippery version.
    • Explain why the non-slippery version converges faster.

  2. Shortest Path Incentives via Step Penalties Currently, in frozen_lake_qlearning.ts, the reward is only received upon reaching the goal (1.0), and normal cells give 0.0 reward. This means the agent has no incentive to find the fastest path, only a safe one.

    • Modify the step function to return a small negative reward (a “step penalty” of -0.01 or -0.02) for transitions that do not end in a hole (H) or the goal (G).
    • Run the Q-learning algorithm again and observe if the average number of steps taken to reach the goal decreases.

  3. Analyzing Discount Factors in Value Iteration In mdp_demo.ts, value iteration is executed with a discount factor of gamma = 0.9.

    • Run the script with different values of gamma, such as 0.1 (highly short-sighted agent) and 0.99 (highly long-sighted agent).
    • Document how these changes affect:
      1. The final optimal policy.
      2. The values assigned to the states.
      3. The number of iterations required for convergence.

  4. Adding Obstacles/Holes to Grid World MDP The 3×3 grid world in mdp_demo.ts has a goal state at index 8 (reward 10) and a penalty state at index 5 (reward -5).

    • Introduce a new “obstacle” state at index 4 (the center cell) which the agent cannot walk through (i.e., any action trying to enter state 4 leaves the agent in its current state, and if the agent starts in state 4, it cannot leave).
    • Adjust the transition probability array P to enforce this obstacle boundary, run valueIteration, and print the updated optimal policy.

Previous

Overview of Image Generation

Up next

Overview of Recommendation Systems (Optional Material)