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

• URL: http://arxiv.org/abs/2510.08882v1
• Date: Fri, 10 Oct 2025 00:25:12 GMT
• Title: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
• Abstract summary: We study decision making with structured observation (DMSO)<n>We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain.
• Score: 41.17780671950473
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs [56.28491566735463]
  Existing algorithms for episodic Markov Decision Processes yield a regret of $smashtildeO(dH2sqrtT)$.<n>We propose an algorithm achieving a regret of $smashtildeO(dH2bar_TsqrtT)$, which recovers the existing bound in the worst case and improves upon it for structured MDPs.
  arXiv  Detail & Related papers  (2026-05-19T12:39:32Z)
• Differentially Private Non-convex Distributionally Robust Optimization [5.6429100834174655]
  Real-world deployments routinely face group imbalances, adversarial perturbations, under which the traditional Empirical Minimization (ERM) framework can degrade severely.<n>This paper provides a comprehensive study of Differential Privacy (DP) optimization.<n>We show that our proposed methods outperform existing approaches for DP minimax optimization.
  arXiv  Detail & Related papers  (2026-02-18T03:00:30Z)
• Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options [35.41703011973504]
  We study online preference-based reinforcement learning (PbRL) with the goal of improving sample efficiency.<n>We propose M-AUPO, an algorithm that selects multiple actions by maximizing the average uncertainty within the offered subset.<n>We prove that M-AUPO achieves a suboptimality gap of $tildemathcalOleft( fracdT sqrt sum_t=1T frac1|S_t| right)$, where $T$ is the total number of rounds, $d$
  arXiv  Detail & Related papers  (2025-10-21T15:11:01Z)
• Large Language Models Imitate Logical Reasoning, but at what Cost? [0.42970700836450487]
  We present a study which evaluates the reasoning capability of frontier Large Language Models over an eighteen month period.<n>We measured the accuracy of three leading models from December 2023, September 2024 and June 2025 on true or false questions.<n>The improvement in performance from 2023 to 2024 can be attributed to hidden Chain of Thought prompting.
  arXiv  Detail & Related papers  (2025-09-16T04:03:42Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Regret Minimization via Saddle Point Optimization [29.78262192683203]
  Decision-estimation coefficient (DEC) was shown to provide nearly tight lower and upper bounds on the worst-case expected regret in structured bandits and reinforcement learning. We derive an anytime variant of the Estimation-To-Decisions (E2D) algorithm. Our formulation leads to a practical algorithm for finite model classes and linear feedback models.
  arXiv  Detail & Related papers  (2024-03-15T15:09:13Z)
• The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization [30.26365073195728]
  We study the generalization performance of gradient methods in the fundamental convex optimization setting. We show that an application of the same construction technique provides a similar $Omega(sqrtd)$ lower bound for the sample complexity of SGD to reach a non-trivial empirical error.
  arXiv  Detail & Related papers  (2024-01-22T15:50:32Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  We introduce a new variant of the Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
  arXiv  Detail & Related papers  (2023-01-19T18:24:08Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.