Polynomial and Fourier Basis in RL

Why Does This Exist?

Continuous control breaks tables. A robot arm or a mountain car lives in an infinite state space, so you cannot store one value per state. Linear methods replace the table with $\hat{v}(s, w) = w^T \phi(s)$: a weight vector $w$ times a feature vector $\phi(s)$ built from the raw state $s$. The features decide what shapes the approximator can draw.

The obvious features are polynomials: $1$, $s_1$, $s_2$, $s_1^2$, $s_1 s_2$, and so on. They fail in practice for three concrete reasons. A TD error in one corner shifts weights that warp predictions everywhere, powers above 2 shoot toward huge magnitudes near the edges, and the features correlate with each other so gradient steps zigzag. Feature construction exists to pick something better, and this page covers the pair most often compared: the polynomial baseline and its replacement.

Konidaris, Osentoski, and Thomas (AAAI 2011) showed the Fourier cosine basis beats polynomials and radial basis functions on standard control benchmarks and matches far heavier learned bases. The idea is simple: normalize each state coordinate into $[0, 1]$, then use cosine harmonics $\cos(\pi c^T s)$ with integer frequency vectors $c$. Every feature stays inside $[-1, 1]$, distinct frequencies are orthogonal, and high frequencies get smaller step sizes automatically.

The one idea you need first. A basis is just a fixed dictionary of shapes whose weighted sum approximates the value surface. Polynomials use powers, tile coding uses overlapping grids, and radial basis functions use bumps. The Fourier basis uses waves. If you know that $w^T \phi(s)$ means one weight per shape, you have enough to follow this page.

Think of It Like This

How It Actually Works

An order $n$ basis in $k$ dimensions has $(n + 1)^k$ features. For $k = 2$ and $n = 1$ that is 4 features; for $k = 2$ and $n = 3$ it is 16. Both bases below share that count. They differ in what each feature computes.

The polynomial baseline

Each feature multiplies powers of the state coordinates. With exponent vector $c_i$ whose entries run $0$ to $n$:

$\phi_i(s) = \prod_{j=1}^{k} s_j^{c_{i,j}}$

For $k = 2$ and $n = 2$ the 9 features are $1$, $s_1$, $s_2$, $s_1^2$, $s_2^2$, $s_1 s_2$, $s_1^2 s_2$, $s_1 s_2^2$, $s_1^2 s_2^2$. Nothing bounds them and nothing orthogonalizes them, so the Hessian of the projected error is ill conditioned and semi gradient TD chases its own tail near the borders.

The Fourier cosine basis

Normalize first: every coordinate $s_j$ is clipped and scaled into $[0, 1]$. Then each feature is one cosine of an integer frequency combination. With coefficient vector $c_i$ whose entries run $0$ to $n$:

$\phi_i(s) = \cos(\pi \, c_i^T s) = \cos\left(\pi \sum_{j=1}^{k} c_{i,j} s_j\right)$

Three properties matter. Boundedness: every $\phi_i(s)$ lies in $[-1, 1]$, so no feature can explode. Orthogonality: distinct frequency vectors give zero inner product over $[0, 1]^k$, which keeps the gradient covariance well conditioned and lets coarse and fine structure learn without fighting. Frequency scaled steps: with base rate $\alpha$ and norm $\lVert c_i \rVert_2$, use $\alpha_i = \alpha$ when the norm is $0$ and $\alpha_i = \alpha / \lVert c_i \rVert_2$ otherwise. High frequency waves oscillate fast over short distances, so they earn smaller steps and the ringing the paper reports with uniform rates disappears.

Worked example

Take a 2D state at normalized coordinates $s = [0.2, 0.8]$, order $n = 1$, base rate $\alpha = 0.01$. The 4 frequency vectors are $[0, 0]$, $[0, 1]$, $[1, 0]$, $[1, 1]$.

Bias term $c = [0, 0]$: dot product $0.0$, feature $\cos(0) = 1.0000$, norm $0$, step $\alpha_0 = 0.0100$.

Vertical mode $c = [0, 1]$: dot product $0.8$, feature $\cos(0.8\pi) = \cos(144^\circ) = -0.8090$, norm $1.0$, step $\alpha_1 = 0.0100$.

Horizontal mode $c = [1, 0]$: dot product $0.2$, feature $\cos(0.2\pi) = \cos(36^\circ) = 0.8090$, norm $1.0$, step $\alpha_2 = 0.0100$.

Diagonal mode $c = [1, 1]$: dot product $1.0$, feature $\cos(\pi) = -1.0000$, norm $\sqrt{2} \approx 1.4142$, step $\alpha_3 = 0.01 / 1.4142 \approx 0.0071$.

So $\phi(s) = [1.0000, -0.8090, 0.8090, -1.0000]$ with steps $[0.0100, 0.0100, 0.0100, 0.0071]$. The diagram draws exactly these four bars. Note the diagonal step is damped about 30 percent: the finest detail moves slowest, which is the point of the scaling rule.

Code

The snippet builds the same 4 features with the standard library only and prints the numbers from the worked example.

1import math2
3
4def fourier_features(s: list[float], order: int = 1) -> list[float]:5    """Cosine features cos(pi * c^T s) for a 2D state in [0, 1]^2."""6    freqs = [(0, 0), (0, 1), (1, 0), (1, 1)]7    out = []8    for c1, c2 in freqs:9        out.append(math.cos(math.pi * (c1 * s[0] + c2 * s[1])))10    return out11
12
13def scaled_alphas(base: float = 0.01) -> list[float]:14    freqs = [(0, 0), (0, 1), (1, 0), (1, 1)]15    out = []16    for c1, c2 in freqs:17        norm = math.sqrt(c1 * c1 + c2 * c2)18        out.append(base if norm == 0 else base / norm)19    return out20
21
22s = [0.2, 0.8]23print([round(v, 4) for v in fourier_features(s)])  # -> [1.0, -0.809, 0.809, -1.0]24print([round(a, 4) for a in scaled_alphas()])      # -> [0.01, 0.01, 0.01, 0.0071]

The first print matches the hand computation $[1.0000, -0.8090, 0.8090, -1.0000]$ and the second matches the damped diagonal step $0.0071$.

Watch Out For

The Quick Version

• Polynomial features multiply state powers and suffer global interference, edge blowups, and correlated gradients.
• Fourier features take $\cos(\pi c^T s)$ over states normalized into $[0, 1]$, giving $(n + 1)^k$ bounded waves.
• Every Fourier feature stays in $[-1, 1]$ and distinct frequencies are orthogonal, so coarse and fine structure stop fighting.
• Step sizes scale as $\alpha / \lVert c \rVert_2$, which damps high frequencies and removes ringing.
• At $s = [0.2, 0.8]$ with order 1 the features are $[1.0, -0.8090, 0.8090, -1.0]$ and the diagonal step is $0.0071$.

What to Read Next

• Feature Construction in RL
• Coarse Coding in RL
• Linear Methods in RL