Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 37 ยท Function Approximation and Deep RL

Tile Coding and Mountain Car

Build tile coding from scratch and train a linear SARSA agent on the Mountain Car task: sparse features, overlapping tilings, step-size scaling and a runnable agent in Python.

In the previous lesson you saw that good features let a few weights approximate a smooth value function. Tile coding is the classic feature scheme for reinforcement learning with continuous states: it is cheap, sparse, easy to tune and surprisingly strong. With it, a plain linear agent can solve tasks that no table could handle.

You will build tile coding from scratch, then use it to solve Mountain Car: an underpowered car sits in a valley and must rock back and forth to build enough momentum to reach the flag on the right hill.

How tile coding works

Imagine laying a grid over the 2D state space (position, velocity). Each cell is a tile. A state falls in exactly one tile, so the feature vector is one-hot: the state aggregation of the last lesson. The trouble is the sharp cell boundaries: two nearby states on opposite sides of a line are treated as strangers.

Tile coding fixes this by using several tilings, each a grid shifted by a small offset. A state activates one tile in each tiling. Two close states share most of their active tiles and differ in a few, so what is learned about one transfers smoothly to the other. The value estimate is simply the sum of the weights of the active tiles:

TEXT
q(s, a) = sum over the active tiles i of w[a][i]

Only n_tilings weights are touched per update (say 8 out of hundreds), which makes it fast. A standard rule for the step size is alpha = 0.5 / n_tilings, because a single update changes the prediction by n_tilings * alpha times the error.

flowchart LR
    S["state (x, v)"] --> T1["tiling 1: tile 17"]
    S --> T2["tiling 2: tile 90"]
    S --> T3["tiling 3: tile 161"]
    T1 --> SUM["sum of 3 weights = q(s, a)"]
    T2 --> SUM
    T3 --> SUM

Each tiling contributes one weight. Shifted tilings give fine resolution from coarse tiles.

Python Nearby states share tiles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Close states share most of their tiles, so a weight update at one of them immediately improves the other; distant states share none and do not interfere.

Mountain Car

The car is pushed by three actions: reverse, coast, or forward. The engine is too weak to climb the hill straight, so the agent must first go away from the goal to gather speed. The reward is -1 every step until the goal, so the agent wants to finish quickly.

The physics are simple enough to write in a few lines. State is (position, velocity):

TEXT
velocity += 0.001 * (action - 1) - 0.0025 * cos(3 * position)
position += velocity                       # both clipped to their ranges

This is a hard exploration problem for tables: random actions almost never reach the flag. But with optimistic zero-initialized weights (every step costs -1, so untried actions look better than they are) a greedy agent explores systematically without any randomness.

Python Linear SARSA with tile coding on Mountain Car

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Early episodes hit the 1000-step cap or take hundreds of steps; within a few dozen episodes the agent usually reaches the flag in roughly 100 to 200 steps. Notice what it had to discover: a non-obvious policy (move left first). The agent never saw a picture of the hill; it only felt the numbers (x, v) and a reward of -1.

Tuning notes

  • Number of tilings: 8 is a common default; more tilings give finer resolution and smoother generalization at higher cost.
  • Tile width: wider tiles generalize more, narrower ones are more precise. Different dimensions may need different widths.
  • Step size: use alpha = c / n_tilings with c around 0.1 to 0.5.
  • Hashing: for high-dimensional states, hash tile coordinates into a fixed-size table instead of enumerating every tile.
  • Scale each dimension to the same range before tiling, as we did with LOW and HIGH.

Common mistakes

  • Using alpha of 0.5 without dividing by the number of tilings; updates overshoot and values blow up.
  • Forgetting the extra row and column of tiles required by shifted grids (BINS + 1), so indices go out of range.
  • Tiling raw, unscaled state values: position ranges over 1.8, velocity over 0.14.
  • Evaluating with eps > 0 and concluding the agent is bad.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does tile coding use several shifted tilings instead of one grid?

    Shifted grids blur the sharp boundaries of a single aggregation and give fine resolution from coarse tiles.
  2. 2. How is q(s, a) computed with tile coding?

    It is a linear function of a sparse binary feature vector, so it is just a sum over the active tiles.
  3. 3. With 8 tilings, why divide the step size by 8?

    All active weights move in the same direction, so the combined change is n_tilings times alpha.
  4. 4. Why can greedy action choice work on Mountain Car when weights start at zero?

    As values fall toward the true negative returns, the greedy choice keeps moving to less-tried, still-optimistic actions.

Summary

  • Tile coding covers the state space with several shifted grids; a state activates one tile per grid.
  • The value is a sum of a few weights, so it is cheap and generalizes between nearby states.
  • Use alpha divided by the number of tilings.
  • On Mountain Car, linear SARSA with tile coding learns the "swing back first" strategy within tens of episodes.
  • Linear features need hand design; the next lesson replaces them with a neural network.

Next: Deep Q-Networks from Scratch