Efficient Reinforcement Learning in Various Environments: from the Idealized to the Realistic

Author(s): Feng, Fei | Advisor(s): Yin, Wotao; Yang, Lin | Abstract: How to achieve efficient reinforcement learning in various training environments is a central challenge in artificial intelligence. This thesis investigates this question on the spectrum of environments from the most idealized type to a fairly realistic one. We use two characteristics to describe the complexity of an environment: 1. how many observations it contains; 2. how difficult it is to capture high rewards. Based on these two scales, we study four types of environments: 1. finite (a small number of) observations plus a generative model (one of the most idealized sample oracles); 2. finite observations plus an approximate model; 3. rich (possibly infinitely many) but structured observations with an online simulation model; 4. general rich observations with an online simulation model. From the first to the last, the problem becomes more and more difficult and significant to solve. This thesis provides novel algorithms/analyses for each setting to improve both statistical and computational efficiency upon prior work.