  We propose an actor-critic algorithm for a family of complex problems arising
in algebraic statistics and discrete optimization. The core task is to produce
a sample from a finite subset of the non-negative integer lattice defined by a
high-dimensional polytope. We translate the problem into a Markov decision
process and devise an actor-critic reinforcement learning (RL) algorithm to
learn a set of good moves that can be used for sampling. We prove that the
actor-critic algorithm converges to an approximately optimal sampling policy.
  To tackle complexity issues that typically arise in these sampling problems,
and to allow the RL to function at scale, our solution strategy takes three
steps: decomposing the starting point of the sample, using RL on each induced
subproblem, and reconstructing to obtain a sample in the original polytope. In
this setup, the proof of convergence applies to each subproblem in the
decomposition.
  We test the method in two regimes. In statistical applications, a
high-dimensional polytope arises as the support set for the reference
distribution in a model/data fit test for a broad family of statistical models
for categorical data. We demonstrate how RL can be used for model fit testing
problems for data sets for which traditional MCMC samplers converge too slowly
due to problem size and sparsity structure. To test the robustness of the
algorithm and explore its generalization properties, we apply it to
synthetically generated data of various sizes and sparsity levels.
