# Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

arXiv: https://arxiv.org/abs/2604.13414 · HTML: https://mlsanity.com/paper/2604.13414/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 15 Apr 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 12 of 12)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [ROCKET: Exceptionally fast and accurate time series classification using random convolutional kernels](https://mlsanity.com/paper/1910.13051/) (2019)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [A Time Series Forest for Classification and Feature Extraction](https://mlsanity.com/paper/1302.2277/) (2013)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)

## Abstract (arXiv)

Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners. When training data exhibits Markov dependence, as in time-series forecasting, reinforcement learning (RL) replay buffers, and spatial grids, this classical guarantee degrades in ways that existing theory does not fully quantify. We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting, together with an adaptive algorithm that matches the rate on a graph-regular subclass. We first establish an information-theoretic lower bound for stationary, reversible, geometrically ergodic chains in fixed ambient dimension, showing that no measurable estimator can achieve excess classification risk better than Omega(√Tmix/n). We then prove that, on the AR(1) witness subclass underlying the lower-bound construction, dependence-agnostic uniform bagging is provably suboptimal with excess risk bounded below by Omega(Tmix/√n), exhibiting a √Tmix algorithmic gap. Finally, we propose adaptive spectral routing, which partitions the training data via the empirical Fiedler eigenvector of a dependency graph and achieves the minimax rate O(√Tmix/n) up to a lower-order geometric cut term on a graph-regular subclass, without knowledge of Tmix. Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions. Consequences for deep RL target variance, scalability via Nystr"om approximation, and bounded non-stationarity are developed as supporting material in the appendix.