mlsanityData to 14 Oct 2026

Learning to sample fibers for goodness-of-fit testing

arXiv 2405.13950 ↗First posted 22 May 2024stat.ML cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We consider the problem of constructing exact goodness-of-fit tests for discrete exponential family models. This classical problem remains practically unsolved for many types of structured or sparse data, as it rests on a computationally difficult core task: to produce a reliable sample from lattice points in a high-dimensional polytope. We translate the problem into a Markov decision process and demonstrate a reinforcement learning approach for learning `good moves' for sampling. We illustrate the approach on data sets and models for which traditional MCMC samplers converge too slowly due to problem size, sparsity structure, and the requirement to use prohibitive non-linear algebra computations in the process. The differentiating factor is the use of scalable tools from linear algebra in the context of theoretical guarantees provided by non-linear algebra. Our algorithm is based on an actor-critic sampling scheme, with provable convergence. The discovered moves can be used to efficiently obtain an exchangeable sample, significantly cutting computational times with regards to statistical testing.

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 11 of its 62 references that are in the map. First posted on arXiv 22 May 2024.

Builds on

11 of 62 references.

References · 11

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  2. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 111
  5. 2014Coauthorship and Citation Networks for Statisticianscited by 22
  6. 2020Convergence Proof for Actor-Critic Methods Applied to PPO and RUDDERcited by 19
  7. 2015Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learningcited by 9
  8. 2022Turning Mathematics Problems into Games: Reinforcement Learning and Gr"obner bases together solve Integer Feasibility Problemscited by 3
  9. 2023Markov bases: a 25 year updatecited by 2
  10. 2016Coauthorship and citation networks for statisticians: Commentcited by 1
  11. 2019What is... a Markov basis?cited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Discrete Compositional Generation via General Soft Operators and Robust Reinforcement Learning
  2. 2026Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces
  3. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
  4. 2026Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
  5. 2026Why Gaussian Diffusion Models Fail on Discrete Data and How to Prevent It?
  6. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  7. 2026Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
  8. 2025Thompson Sampling via Fine-Tuning of LLMs