Exploration while learning representations is one of the main challenges Deep
 Reinforcement Learning (DRL) faces today. As the learned representation is dependant in the observed data, the exploration strategy has a crucial role. The popular DQN algorithm has improved significantly the capabilities of Reinforcement
 Learning (RL) algorithms to learn state representations from raw data, yet, it uses
 a naive exploration strategy which is statistically inefficient. The Randomized
 Least Squares Value Iteration (RLSVI) algorithm (Osband et al., 2016), on the
 other hand, explores and generalizes efficiently via linearly parameterized value
 functions. However, it is based on hand-designed state representation that requires
 prior engineering work for every environment. In this paper, we propose a Deep
 Learning adaptation for RLSVI. Rather than using hand-design state representation, we use a state representation that is being learned directly from the data by a
 DQN agent. As the representation is being optimized during the learning process,
 a key component for the suggested method is a likelihood matching mechanism,
 which adapts to the changing representations. We demonstrate the importance of
 the various properties of our algorithm on a toy problem and show that our method
 outperforms DQN in five Atari benchmarks, reaching competitive results with the
 Rainbow algorithm. In Reinforcement Learning (RL), an agent seeks to maximize the cumulative rewards obtained from interactions with an unknown environment (Sutton et al., 1998) . Since the agent can learn only by its interactions with the environment, it faces the exploration-exploitation dilemma: Should it take actions that will maximize the rewards based on its current knowledge or instead take actions to potentially improve its knowledge in the hope of achieving better future performance. Thus, to find the optimal policy the agent needs to use an appropriate exploration strategy. Classic RL algorithms were designed to face problems in the tabular settings where a table containing a value for each state-action pair can be stored in the computer's memory. For more general settings, where generalization is required, a common practice is to use hand-designed state representation (or state-action), upon which a function approximation can be learned to represent the value for each state and action. RL algorithms based on linear function approximation have demonstrated stability, data efficiency and enjoys convergence guarantees under mild assumptions (Tsitsiklis & Van Roy, 1997; Lagoudakis & Parr, 2003) . They require that the desired learned function, e.g. Qfunction, will be a linear combination of the state representation. This is, of course, a hard constraint as the representation is hand-designed, where the designer often does not know how the optimal value-function will look like. Furthermore, hand-designed representation is environment-specific and requires re-designing for every new environment. The DQN algorithm (Mnih et al., 2015) has changed RL. Using Deep Neural Networks (DNN) as function approximators, the DQN algorithm enabled the learning of policies directly from raw highdimensional data and led to unprecedented achievements over a wide variety of domains (Mnih et al., 2015) . Over the years, many improvements to DQN were presented, suggesting more fitting network architectures (Wang et al., 2015) , reducing overestimation (Van Hasselt et al., 2016; Anschel et al., 2017) or improving its data efficiency . Despite its great success, DQN uses the overly simple -greedy strategy for exploration. This strategy is one of the simplest exploration strategies that currently exist. The agent takes random action with probability and takes the optimal action according to its current belief with probability 1 − . This strategy is commonly used despite its simplicity and proven inefficiency (Osband et al., 2016) . The main shortcoming of -greedy and similar strategies derives from the fact that they do not use observed data to improve exploration. To explore, it takes a completely random action, regardless of the experience obtained by the agent. Thompson Sampling (TS) (Thompson, 1933) , is one of the oldest heuristics to address the 'exploration/exploitation' trade-off in sequential decision-making problems. Its variations were proposed in RL (Wyatt, 1998; Strens, 2000) and various bandits settings (Chapelle & Li, 2011; Scott, 2010) . For Multi-Armed Bandit (MAB) problems, TS is very effective both in theory (Agrawal & Goyal, 2012; and practice (Chapelle & Li, 2011) . Intuitively, TS randomly takes actions according to the probability it believes to be optimal. In practice, a prior distribution is assumed over the model's parameters p(w), and a posterior distribution p(w|D) is computed using the Bayes theorem, where D is the observed data. TS acts by sampling models from the posterior distribution, and plays the best action according to these samples. Randomized Least Squares Value Iteration (Osband et al., 2016) is an RL algorithm which uses linear function approximation and is inspired by Thompson Sampling. It explores by sampling plausible Q-functions from uncertainty sets and selecting the action that optimizes the sampled models. This algorithm was proven to be efficient in tabular settings, with a bound on the expected regret that match the worst-case lower bound up to logarithmic factors. More importantly, it demonstrates efficiency even when generalization is required. Alas, as it assumes a linearly parametrized value function on a hand-designed state representation, the success of this algorithm crucially depends on the quality of the given state representation. In this paper, we present a new DRL algorithm that combines the exploration mechanism of RLSVI with the representation learning mechanism of DQN; we call it the Deep Randomized Least Squares Value Iteration (DRLSVI) algorithm. We use standard DQN to learn state representation and explores by using the last layer's activations of DQN as state representation for RLSVI. To compensate for the constantly changing representation and the finite memory of DQN, we use a likelihood matching mechanism, which allows the transfer of information held by an old representation regarding past experience. We evaluate our method on a toy-problem -the Augmented Chain environment -for a qualitative evaluation of our method on a small MDP with a known optimal value function. Then, we compare our algorithm to the DQN and Rainbow algorithms on several Atari benchmarks. We show that it outperforms DQN both in learning speed and performance. A Deep Learning adaptation to RLSVI was presented which learn the state representation directly from the data. We demonstrated the different properties of our method in experiments and showed the promise of our method. We hope to further reduce the complexity and running time of our algorithm in future work.
A Deep Learning adaptation of Randomized Least Squares Value Iteration
{"src": "scitldr-AIC_train", "paper_id": "Syetja4KPH"}