An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

AI summary

Overview

Research area: theoretical machine learning and reinforcement learning theory, specifically online decision making with structured observations (DMSO), decision-estimation coefficients (DEC), and regret bounds for stochastic, hybrid, and adversarial Markov decision processes (MDPs). Technical level: Advanced. Scope: The paper introduces Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain, then uses it to derive improved model-free regret bounds for stochastic and hybrid MDPs with bandit feedback.

The provided content reports no datasets or empirical benchmark evaluations; the paper is a theoretical work.

What This Paper Is About

Previous DEC work characterized DMSO complexity but left a gap between regret upper and lower bounds that scales with the size of the model class, written as log|ℳ|. Foster et al. (2023b) introduced optimistic DEC to reduce this to the size of the value-function class, but their optimism-based exploration was only known to handle stochastic settings, and it was unclear whether it extends to adversarial settings. This paper asks whether model-free learning can handle adversarial and hybrid environments without optimism, and answers by introducing Dig-DEC and improved online function-estimation procedures.

Key Contributions

1. Introduces Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Removing optimism allows it to handle adversarial environments without explicit reward estimators.
2. Obtains the first model-free regret bounds for hybrid MDPs with bandit feedback under linear reward and several general transition structures, resolving the main open problem left by Liu et al. (202

Authors’ abstract

We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.