Spectral Drift Entropy (SDE)

A new axis of difficulty for non-stationary reinforcement learning.

---

Overview

Non-stationary RL research characterises environment change by drift magnitude — total variation budget, Lipschitz rate, switching cost. But this conflates two fundamentally different regimes:

Regime	Example	Structure	Learnable?
Periodic	Seasonal demand, diurnal robotics	Concentrated spectrum	✓ Pre-adapt
Chaotic	Random shocks, adversarial perturbations	Diffuse spectrum	✗ React only

We introduce Spectral Drift Entropy (SD) — the normalised Shannon entropy of the temporal power spectrum of per-state-action drift — which formally separates these regimes orthogonally to drift magnitude.

---

Key Results

Finding	Value
SD predicts SDAR regret	r = +0.401, p < 0.001, n = 100
SDAR improvement — periodic (SD=0.16)	8.0× over fixed policy
SDAR improvement — chaotic (SD=0.90)	1.9× over fixed policy
SD ordering preserved across amplitudes	✓ All 5 levels
SD ordering preserved across |S| = 10, 20, 30	✓ All sizes

---

Theoretical Contributions

1. Hybrid value degradation bound — policy error bounded by B_t · g(SD), where g(SD) is derived from the Kolmogorov–Szegő prediction error formula under an LTI drift model.

2. Regret separation theorem — equal drift budget B_T yields Õ(√(B_T T)) regret for periodic environments vs Ω(B_T T^{1/3}) for chaotic (minimax). Gap grows with horizon.

3. SD bounds drift predictability — SD is a formal instance of the predictability measure of Rakhlin & Sridharan (2013), grounding the framework in online learning theory.

4. Orthogonality proposition — two MDPs with identical B_T can have SD = 0 and SD = 1, proving SD and magnitude are independent axes.

5. SD-Adaptive Restart (SDAR) — online algorithm using estimated SD to calibrate restart thresholds; no prior knowledge of drift type required.

---

Repo Structure

spectral-drift-entropy/
├── src/
│   ├── core.py           # SD computation, MDP utils, value iteration
│   └── sdar.py           # SDAR algorithm
├── experiments/
│   ├── run_main.py       # Main: SD vs SDAR across 100 environments
│   ├── run_additional.py # Value error, amplitude robustness, threshold sensitivity
│   └── run_scalability.py# Scalability: |S| = 10, 20, 30
├── paper/
│   └── SDE_Paper.pdf     # Full paper (TMLR submission)
├── results/              # JSON outputs (populated by experiments)
├── figures/              # PDF figures (populated by experiments)
├── assets/               # README images
├── requirements.txt
├── reproduce.sh          # One-command full reproduction
└── README.md

---

Quickstart

git clone https://github.com/Aarav500/spectral-drift-entropy
cd spectral-drift-entropy
pip install -r requirements.txt
bash reproduce.sh        # runs all experiments, ~50 min

Individual experiments

# Main result: SD vs SDAR regret (n=100, ~30 min)
python experiments/run_main.py

# Additional: value error, robustness, threshold (~15 min)
python experiments/run_additional.py

# Scalability: S=10,20,30 (~2 min)
python experiments/run_scalability.py

---

Core API

from src.core import compute_sd, inject_drift, make_base_mdp
from src.sdar import SDARAgent

# Compute Spectral Drift Entropy
P_base, R = make_base_mdp(S=10, A=4, seed=0)
P_seq = inject_drift(P_base, drift_type='periodic_low', T=100)
sd = compute_sd(P_seq, P_base)
print(f"SD = {sd:.3f}")   # SD = 0.158 for periodic, ~0.90 for chaotic

# Run SDAR
agent = SDARAgent(window=20, threshold=0.3)
# ... standard RL loop, call agent.maybe_restart(bellman_error) each step

compute_sd(P_seq, P_base) — the key function:

• Uses cumulative deviation ||P_t - P_0||_1 (not first differences)
• Computes normalised FFT entropy over the resulting trajectory
• Returns scalar in [0, 1]: 0 = pure sinusoid, 1 = white noise

---

Reproducing Figures

Figure	Script	Output
Fig 1: SD vs SDAR regret (main)	run_main.py	figures/fig_main.pdf
Fig 2: Regret curves	run_main.py	figures/fig_regret.pdf
Fig 3: Theory comparison	(paper LaTeX)	figures/fig_theory.pdf
Fig 4: Value error over time	run_additional.py	figures/fig_value_error.pdf
Fig 5: Threshold sensitivity	run_additional.py	figures/fig_hyperparam.pdf
Fig 6: Scalability	run_scalability.py	figures/fig_scalability.pdf

---

Expected Outputs

After running all experiments:

results/
├── sde_results_v4.json     # Main: r=+0.401, p<0.001
├── sde_additional.json     # Value error: 11x gap periodic vs chaotic
└── sde_scalability.json    # Ordering preserved at S=10,20,30

---

Citation

@article{shah2025spectral,
  title={Spectral Drift Entropy: A New Axis of Difficulty
         for Non-Stationary Reinforcement Learning},
  author={Shah, Aarav},
  journal={Transactions on Machine Learning Research},
  year={2025}
}

---

License

MIT License. See LICENSE.

---

University of California, Riverside · ashah264@ucr.edu