Nearly Solving Intractable Problems via Mean-Field Convergence: Two Examples

In this talk, we will discuss two examples with a common theme: 1. A computational problem which is provably hard due to combinatorial structure. 2. There exists a continuum limit for large sizes. 3. The analytic structure present in the continuum limit can be leveraged to nearly solve the original problem. First we will discuss the sampling exponential random graphs in low temperature, for which any local markov chain has to suffer an exponential mixing time. By relaxing the notion of mixing form worst case mixing to `meta-stable mixing', we show that Glauber dynamics with the right initialization can sample this model up-to an exponentially small TV distance. Next we will consider the problem of planning restless multi-armed bandits, which is a multi-agent reinforcement learning problem with resource constraints. While this is known to be PSPACE hard, heuristics like Whittle index policies are known to be nearly optimal under certain conditions. We will discuss some natural instances where Whittle index policies fail despite indexibility, and introduce the provably near-optimal mean-field planning algorithm.