Statistical learning with latent variables : mixture models and reinforcement learning

Statistical learning with missing or hidden information is ubiquitous in many practical problems. For example, the success of a certain medical treatment can largely depend on the unknown conditions of patients, or some parts of data could be censored to protect the privacy of individuals. In contrast to problems with full information which often have simple and tractable solutions, the existence of such latent variables often plants the intractable non-convexity complicating the landscape of the problem from both statistical and computational aspects. While both aspects are important, this thesis put more emphasis on understanding the statistical challenges raised by latent variables. This thesis consists of two main parts. In Part I, we consider the parameter estimation in finite mixture models, and in particular, we study the Expectation-Maximization (EM) algorithm for learning the maximum likelihood estimator (MLE) given i.i.d. samples from mixtures of Gaussian distributions. In Part II, we turn our focus to reinforcement learning (RL), and study the sample-complexity of learning a near-optimal policy when an important context of an environment is not observable. We now give a brief overview of these two parts. Part I. The first part of the thesis studies the convergence and statistical behaviors of EM in largely two fundamental settings: one setting concerns a mixture consisting of two symmetric components, and the other setting concerns a mixture of an arbitrary number of well-separated components. Chapter 1 describes some background and notation that would be relevant to the two settings. In Chapter 2,we focus on a mixture of two linear regressions (2-MLR), and completely characterize the global optimality of EM: we show that starting from any randomly initialized point, the EM algorithm converges to the true parameter at the known minimax statistical rates in all parameters under all signal-to-ratio (SNR) regimes. In Chapter 3, we focus on two canonical mixture problems: a mixture of K ≥ 3 well-separated Gaussians (K-GMM) and linear regressions (K-MLR). For these problems, we provide a rigorous (local) convergence guarantee for the EM algorithm when the mixture components are well-separated. Notably, we establish the minimax statistical rate of EM (and thus MLE) in all problem parameters for these two examples. Part II. In the second part of the thesis, we consider learning a near-optimal policy in Latent Markov Decision Processes (LMDPs). In an LMDP, an MDP is randomly drawn from a set of M possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. As a starting point, we show that a general instance of LMDPs with S states and A actions requires at least Ω(SA)[superscript M] episodes to even approximate the optimal policy. This lower bound suggests that the problem is only tractable when additional assumptions are provided with growing number of contexts M = ω(1), or when the number of contexts are small M = O(1). We describe a more detailed overview and backgrounds in Chapter 4. In Chapter 5, we first prove the lower bound of Ω(SA)[superscript M] in the absence of further assumptions. Then we focus on the M = ω(1) regime, where we consider sufficient assumptions under which learning good policies requires polynomial number of episodes in M. We show that the key link is a notion of separation between the MDP system dynamics. With sufficient separation, we provide an efficient algorithm with local guarantee, i.e., providing a sublinear regret guarantee when we are given a good initialization. The need for initialization can be removed if a certain statistical sufficiency assumption is provided. In Chapter 6, we consider learning a near-optimal policy in reward-mixing MDPs (RMMDPs), which itself is a special case of LMDPs with common state transitions probabilities across contexts. Without any assumptions, no sample upper bound is known even for this setting. We first study the problem of learning a near optimal policy for two reward-mixing MDPs, i.e., M = 2. Unlike existing approaches that rely on strong assumptions on the dynamics, we make no assumptions and study the problem in full generality. Indeed, with no further assumptions, even for two switching reward-models, the problem requires several new ideas beyond existing algorithmic and analysis techniques for efficient exploration. Finally, in Chapter 7, we show that the moment-matching idea can be applied when the system is in a simpler latent multi-armed bandit (LMAB) setting (or equivalently when S = 1). Unlike in general LMDPs which suffers Ω(A)[superscript M] lower bound, we show that the polynomial sample complexity in A is possible in LMABs.Electrical and Computer Engineerin