RL Theory & Markov Decision Processes
Regret Bounds with Problem-Dependent Constants Removed: Minimax Characterization of the Gap Between Instance-Independent and Instance-Dependent Guarantees
Generated automatically from the limitations stated in 7 papers (NeurIPS, ICML, ICLR), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.
The problem
Every one of these bounds is technically instance-independent, but each carries a "constant" — κ, exponential variation budgets, hitting-time factors, (1−γ)^−6, K^n, binomial coefficients — that is itself an instance-dependent quantity scaling exponentially or polynomially-huge on exactly the instances practitioners care about. The result is that published algorithms are provably efficient only on benign instances, and no one knows which of these constants are artifacts of analysis versus intrinsic hardness. Without a theory of which dependence is real, practitioners cannot tell whether a tight-constraint CMDP or a large-state bandit is fundamentally hard or merely badly analyzed.
Why it matters
Algorithms whose guarantees remain meaningful on hard instances, and a decision procedure telling users when a setting is provably hopeless rather than merely badly bounded.
Ways to approach it
Prior-work checks are free with an account. Results someone already ran are shown to everyone.
- 1
Instance-by-instance audit: pick one representative bound (e.g., the κ-dependent CMDP regret) and construct lower-bound instances showing the dependence is either information-theoretic or an artifact. Measure: the gap between achieved regret and the instance's information-theoretic optimum.
- 2
Instance-dependent minimax framework: define for each setting the minimal worst-case regret achievable given the instance's actual parameters (mixing rates, constraint slack, dimension), and prove matching upper bounds that replace the offending constants with measurable, per-instance quantities. Measure: regret on standard benchmark instances versus prior bounds.
- 3
Adaptive horizon/relaxation study: prove whether the exponential-in-d or K^n terms can be traded for logarithmic terms under assumptions strictly weaker than the current ones (unichain, bounded variation). Measure: sample complexity under adversarial instances.
Have a different approach?
Describe how you would tackle this problem and we'll look for papers that already do it. Free; your text stays private.
Why it might fail
The lower-bound machinery may show the exponential dependencies are information-theoretically necessary, collapsing the project into an impossibility result rather than better algorithms — and even then, the instances proving it may be measure-zero pathologies that don't reflect practice.
Sub-problems
Polynomial-Regret Bounds for High-Dimensional Strategic and Multi-Agent Bandits
Current regret bounds in strategic contextual bandits and multi-agent action-feedback games scale exponentially with context dimension, game depth, or state-action sizes. This exponential dependence renders theoretical guarantees vacuous and algorithms practically unusable for problems with more than a few states or features. Practitioners are blocked from deploying provably no-regret learning algorithms in realistic, high-dimensional economic mechanisms and strategic environments.
Evidence
Each paper's own statement of the limitation, verbatim.
- Learning to Play Multi-Follower Bayesian Stackelberg GamesICLR 2026
Action feedback regret retains an exponential factor in either n (K^n) or L (n^L K^L A^{2L}).
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic ApproachNeurIPS 2025
Regret bound scales with C_hit and C_tar (hitting-time constants of the unichain chain), which can be large and are problem-dependent; the paper does not relax the unichain assumption itself (multichain MDPs excluded)
- Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPsALT 2024
Regret has large polynomial dependencies on H, S, A, β, and 1/(1-γ) (up to (1-γ)^-6 when γ→1); the authors argue linear-in-S dependency is unavoidable in this framework
- Pausing Policy Learning in Non-stationary Reinforcement LearningICML 2024
The regret bound relies on Assumption 3.1 that local variation budgets grow at exponential order with known/estimable constants (k_r, k_p, B_max), which may not hold for environments with abrupt or heavy-tailed changes; Theorem 5.8 also has no closed-form solution and requires numerical solution.
- Online Bayesian Persuasion Without a ClueNeurIPS 2024
Regret bound has exponential dependence on min(d, n) via the binomial coefficient, making the algorithm practical only when the number of states or actions is small
- Strategic Apple TastingNeurIPS 2023
Regret of SA-OLS depends on constant c1(d,δ) scaling exponentially in context dimension d (~ (1−δ)^{d/2}/d²), problematic when T is small or unknown; using 'unclean' data makes OLS inconsistent
- Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise ConstraintsICML 2023
Regret bound has a 1/κ² dependence in the additive term, so stringent safety margins (small κ) inflate the constant regret cost; prior CMDP methods also suffer κ dependence but this limits practicality for tight constraints.
Nearest existing work
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision ProcessNeurIPS 2024
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based PerspectiveCOLT 2021
- Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic EnvironmentsICML 2023
- Beyond No Regret: Instance-Dependent PAC Reinforcement LearningCOLT 2022
- Instance-optimal PAC Algorithms for Contextual BanditsNeurIPS 2022
- Settling the sample complexity of online reinforcement learningCOLT 2024
- Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function BoundsICML 2019
- Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function ApproximationAISTATS 2024
- Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function ApproximationAISTATS 2024
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior SamplingICML 2024
- Nearly Minimax-Optimal Regret for Linearly Parameterized BanditsCOLT 2019
- Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational EfficiencyCOLT 2023
- Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision ProcessesUAI 2024
- Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPsCOLT 2026
- Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment DesignNeurIPS 2022
Related open problems
RL Theory & Markov Decision Processes
Empirical Robustness and Scalability Evaluation of Provably Efficient RL Algorithms
A wide range of theoretical reinforcement learning algorithms offer provable sample-complexity guarantees, yet their empirical validation is almost exclusively restricted to synthetic tabular MDPs with fewer than 30 states. Because these methods have not been evaluated across larger, standardized, or higher-dimensional environments, it remains unknown whether their theoretical efficiency properties hold in practice. Without systematic cross-domain testing, the community lacks evidence on whether provably efficient exploration and representation mechanisms scale beyond toy sandbox problems.
RL Theory & Markov Decision Processes
Sample-Efficient Reinforcement Learning Under Markovian Trajectory Sampling Without a Generative Model
Theoretical analysis in these MDP frameworks relies on a generative model that provides independent transition samples for arbitrary state-action queries. In real-world physical systems and streaming applications, arbitrary state resetting is impossible and data must be gathered along continuous online or episodic trajectories. As a result, existing sample complexity and convergence guarantees fail to hold under realistic Markovian data generation, leaving theoretical bounds disconnected from deployable online settings.
RL Theory & Markov Decision Processes
Reinforcement Learning Algorithms Without Generative Model and Reset Oracles
A wide class of theoretical and model-based RL methods rely on access to a generative model or simulator capable of querying arbitrary state-action pairs and performing instant resets. In physical systems, streaming data settings, and non-resettable environments, arbitrary state querying is impossible, restricting these algorithms to synthetic simulations. Consequently, the theoretical guarantees and policy optimization mechanisms derived under generative oracle assumptions fail completely when deployed in realistic single-trajectory or trajectory-constrained online environments.