summaries: In many real world applications for RL such as medicine, there are limits on the number of policies from which we can simulate data. This paper proposes an approach that adaptively decides when to update the simulation policy, based on the difference between it and the current learned policy. Experiments on a medical treatment environment and Atari show that the approach obtains similar performance to on-policy RL with fewer changes of the simulation policy. In the RL context, this paper aims at designing a generic solution for reducing the number of policy switches during training (called switching cost) while maintaining the performance. This study is done in the context of deep reinforcement learning. A few generic baselines solutions are provided as well as a more complex solution that empirically outperforms the baselines. This paper studies RL with low switching cost under the deep RL setting. It points out several naive algorithms like switching after a certain number of steps and then propose a new heuristic. This heuristic learns a new policy offline using the experience replay the behavior collected and switches the behavior policy once the similarity of the feature embeddings of the current state by these two policies becomes large. The paper also makes an attempt to provide a theoretical justification for a better understanding of the heuristic. This method might outperform the naive algorithms by some margin, if any. It would be a more interesting manuscript if some stronger results could be provided from the perspective of any of theory, experiments, or applications.
abstractText: We initiate the study on deep reinforcement learning problems that require low switching cost, i.e., a small number of policy switches during training. Such a requirement is ubiquitous in many applications, such as medical domains, recommendation systems, education, robotics, dialogue agents, etc, where the deployed policy that actually interacts with the environment cannot change frequently. Our paper investigates different policy switching criteria based on deep Q-networks and further proposes an adaptive approach based on the feature distance between the deployed Q-network and the underlying learning Q-network. Through extensive experiments on a medical treatment environment and a collection of the Atari games, we find our feature-switching criterion substantially decreases the switching cost while maintains a similar sample efficiency to the case without the low-switching-cost constraint. We also complement this empirical finding with a theoretical justification from a representation learning perspective.
references.authors: Ki Uhn Ahn Cheol Soo Park
references.title: Application of deep q-networks for model-free optimal control balancing between different hvac systems
references.venue: Science and Technology for the Built Environment,
references.authors: Tao Ao Jiong Shen Xichui Liu
references.title: The application of dqn in thermal process control
references.venue: Chinese Control Conference (CCC),
references.authors: Peter Auer Nicolo Cesa-Bianchi Paul Fischer
references.title: Finite-time analysis of the multiarmed bandit problem
references.venue: Machine learning,
references.authors: Yu Bai Tengyang Xie Nan Jiang Yu-Xiang Wang
references.title: Provably efficient q-learning with low switching cost
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Marc G. Bellemare W. Dabney R. Munos
references.title: A distributional perspective on reinforcement
references.venue: learning. ArXiv,
references.authors: Nicolo Cesa-Bianchi Ofer Dekel Ohad Shamir
references.title: Online learning with switching costs and other adaptive adversaries
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Shi-Yong Chen Yang Yu Qing Da Jun Tan Hai-Kuan Huang Hai-Hong Tang
references.title: Stabilizing reinforcement learning in dynamic environment with application to online recommendation
references.venue: In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Shixiang Gu Ethan Holly Timothy Lillicrap Sergey Levine
references.title: Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates
references.venue: IEEE international conference on robotics and automation (ICRA),
references.authors: H.V. Hasselt A. Guez D. Silver
references.title: Deep reinforcement learning with double q-learning
references.venue: In AAAI,
references.authors: Matteo Hessel Joseph Modayil Hado van Hasselt Tom Schaul Georg Ostrovski Will Dabney Dan Horgan Bilal Piot Mohammad Gheshlaghi Azar David Silver
references.title: Rainbow: Combining improvements in deep reinforcement learning
references.venue: In AAAI,
references.authors: Natasha Jaques Asma Ghandeharioun Judy Hanwen Shen Craig Ferguson Agata Lapedriza Noah Jones Shixiang Gu Rosalind Picard
references.title: Way off-policy batch deep reinforcement learning of implicit human preferences in dialog
references.venue: arXiv preprint arXiv:1907.00456,
references.authors: Sascha Lange Thomas Gabel Martin Riedmiller
references.title: Batch reinforcement learning
references.venue: In Reinforcement learning,
references.authors: Sergey Levine Aviral Kumar George Tucker Justin Fu
references.title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems
references.venue: arXiv preprint arXiv:2005.01643,
references.authors: Travis Mandel Yun-En Liu Sergey Levine Emma Brunskill Zoran Popovic
references.title: Offline policy evaluation across representations with applications to educational games
references.venue: In AAMAS,
references.authors: Tatsuya Matsushima Hiroki Furuta Yutaka Matsuo Ofir Nachum Shixiang Gu
references.title: Deploymentefficient reinforcement learning via model-based offline optimization
references.venue: arXiv preprint arXiv:2006.03647,
references.authors: V. Mnih K. Kavukcuoglu D. Silver Andrei A. Rusu J. Veness Marc G. Bellemare A. Graves Martin A. Riedmiller Andreas K. Fidjeland Georg Ostrovski S. Petersen C. Beattie A. Sadik Ioannis Antonoglou H. King D. Kumaran Daan Wierstra S. Legg Demis Hassabis
references.title: Humanlevel control through deep reinforcement learning
references.venue: Nature, 518:529–533,
references.authors: Satinder P Singh Tommi Jaakkola Michael I Jordan
references.title: Reinforcement learning with soft state aggregation
references.venue: In Advances in neural information processing systems,
references.authors: R. Sutton
references.title: Learning to predict by the methods of temporal differences
references.venue: Machine Learning,
references.authors: R. Sutton A. Barto
references.title: Reinforcement learning: An introduction
references.venue: IEEE Transactions on Neural Networks,
references.authors: Haoran Tang Rein Houthooft Davis Foote Adam Stooke Xi Chen Yan Duan John Schulman F. Turck P. Abbeel
references.title: Exploration: A study of count-based exploration for deep reinforcement
references.venue: learning. ArXiv,
references.authors: Ziyu Wang T. Schaul Matteo Hessel H.V. Hasselt Marc Lanctot N.D. Freitas
references.title: Dueling network architectures for deep reinforcement learning
references.authors: Zihan Zhang Xiangyang Ji Simon S. Du
references.title: Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon
references.venue: arXiv preprint arXiv:2009.13503,
references.authors: Zihan Zhang Yuan Zhou Xiangyang Ji
references.title: Almost optimal model-free reinforcement learning via reference-advantage decomposition, 2020b
sections.heading: 1 INTRODUCTION
sections.text: Reinforcement learning (RL) is often used for modeling real-world sequential decision-making problems such as medical domains, personalized recommendations, hardware placements, database optimization, etc. For these applications, oftentimes it is desirable to restrict the agent from adjusting its policy frequently. In medical domains, changing a policy requires a thorough approval process by experts. For large-scale software and hardware systems, changing a policy requires to redeploy the whole environment. Formally, we would like our RL algorithm admits a low switching cost. In this setting, it is required that the deployed policy that interacts with the environment cannot change many times.
  In some real-world RL applications such as robotics, education, and dialogue system, changing the deployed policy frequently may cause high costs and risks. Gu et al. (2017) trained robotic manipulation by decoupling the training and experience collecting threads; Mandel et al. (2014) applied RL to educational games by taking a data-driven methodology for comparing and validating policies offline, and run the strongest policy online; Jaques et al. (2019) developed an off-policy batch RL algorithms for dialog system, which can effectively learn in an offline fashion, without using different policies to interact with the environment. All of these work avoid changing the deployed policy frequently as they try to train the policy offline effectively or validate the policy to determine whether to deploy it online.
  For RL problem with a low switching cost constraint, the central question is how to design a criterion to decide when to change the deployed policy. Ideally, we would like this criterion to have the following four properties:
  1. Low switching cost: This is the purpose of this criterion. An algorithm equipped with this policy switching criterion should have low switching cost.
  2. High Reward: Since the deployed policy determines the collected samples and the agent uses fewer deployed policies, the collected data may not be informative enough to learn the optimal policy with high reward. We need this criterion to deploy policies that can collect informative samples.
  3. Sample Efficiency: Since the agent only uses a few deployed policies, there may be more redundant samples, which will not be collected if the agent switches the policy frequently. We would like algorithms equipped with a criterion with similar sample efficiency as the case without the low switching cost constraint.
  4. Generality: We would like this criterion to be effective not only on a specific task but also broadly effective on a wide range of tasks.
  In this paper, we take a step toward this important problem. We focus on designing a principled policy switching criterion for deep Q-networks (DQN) learning algorithms, which have been widely used in applications. For example, Ahn & Park (2020) apply DQN to control balancing between different HVAC systems, Ao et al. (2019) propose a thermal process control method based on DQN, and Chen et al. (2018) try to apply it to online recommendation. Notably these applications all require low switching cost.
  Our paper conducts a systematic study on DQN with low switching cost. Our contributions are summarized below.
  Our Contributions
  • We conduct the first systematic empirical study on benchmark environments that require modern reinforcement learning algorithms. We test two naive policy switching criteria: 1) switching the policy after a fixed number of steps and 2) switching the policy after an increasing step with a fixed rate. We find that neither criterion is a generic solution because sometimes they either cannot find the best policy or significantly decrease the sample efficiency.
  • Inspired by representation learning theory, we propose a new feature-based switching criterion that uses the feature distance between the deployed Q-network and the underlying learning Q-network. Through extensive experiments, we find our proposed criterion is a generic solution – it substantially decreases the switching cost while maintains a similar performance to the case without the low-switching-cost constraint.
  • Along the way, we also derive a deterministic Rainbow DQN (Hessel et al., 2018), which may be of independent interest.
  Organization This paper is organized as follows. In Section 2, we review related work. In Section 3, we describe our problem setup and review necessary backgrounds. In Section 4, we describe deterministic Rainbow DQN with the low switching cost constraint. In Section 5, we introduce our feature-based policy switching criterion and its theoretical support. In Section 6, we conduct experiments to evaluate different criteria. We conclude in Section 7 and leave experiment details to appendix.
sections.heading: 2 RELATED WORK
sections.text: Low switching cost algorithms were first studied in the bandit setting (Auer et al., 2002; CesaBianchi et al., 2013). Existing work on RL with low switching cost is mostly theoretical. To our knowledge, Bai et al. (2019) is the first work that studies this problem for the episodic finite-horizon tabular RL setting. Bai et al. (2019) gave a low-regret algorithm with an O ( H3SA log (K) ) local switching upper bound where S is the number of stats, A is the number of actions, H is the planning horizon and K is the number of episodes the agent plays. The upper bound was improved in Zhang et al. (2020b;a).
  The only empirical study on RL with switching cost is Matsushima et al. (2020), which proposed a concept of deployment efficiency and gave a model-based algorithm. During the training process, the algorithm fixes the number of deployments, trains a dynamics model ensemble, and updates the deployed policy alternately. After each deployment, the deployed policy collects transitions in the real environment to enhance the models, and then the models optimize the policy by providing imagined trajectories. In other words, they reduce the number of deployments by training on simulated environments. Our goal is different: we design a criterion to decide when to change the deployed policy, and this criterion could be employed by model-free algorithms.
  There is a line of work on offline RL (also called Batch RL) methods, where the policy does not interact with the environment directly and only learns from a fixed dataset (Lange et al., 2012; Levine et al., 2020). Some methods Interpolate offline and online methods, i.e., semi-batch RL
  algorithms (Singh et al., 1995; Lange et al., 2012), which update the policy many times on a large batch of transitions. However, the switching cost is not their focus.
sections.heading: 3 PRELIMINARIES
sections.heading: 3.1 MARKOV DECISION PROCESS
sections.text: Throughout our paper, we consider the episodic Markov decision model (S,A, H, P, r). In this model, S is the state space, A is the action space, H ∈ Z+ is the planning horizon. P is the transition operator where P (x′|x, a) denotes the transition probability of taking action a from state x to state x′. r : S ×A → R is the reward function. A policy is a mapping from a state to an action, π : S → A. In this paper, we focus on deterministic policies as required by motivating applications. The dynamics of the episodic MDP can be view as the interaction of an agent with the environment periodically. We let K be the total number of episodes the agent plays. At the beginning of an episode k ∈ [K], the agent chooses a policy πk. The initial xk1 ∈ S is sampled from a distribution, and the agent is then in step 1. At each step h ∈ [H] in this episode, based on the current state xkh ∈ S the agent chooses the action akh = πk(xkh). The environment will give the reward for the step r(xkh, a k h) and move the agent to the next state xh+1 ∼ P (·|xkh, akh). The episode automatically ends when the agent reaches the step H + 1.
  Q-function is used to evaluate the long-term value for the action a and subsequent decisions. The Q-function of a policy π at time step h is defined as follows:
  Qπh(x, a) := rh(x, a) + E
  [ H∑
  i=h+1
  r (xi, π (xi)) ∣∣∣∣∣xh = x, ah = a ]
  (1)
  The goal of this agent is to find a policy π∗ which maximizes the expected reward, π∗ = arg maxπ Eπ [∑H h=1 rh ] . Ideally, we want to use a few episodes (K) as possible to learn π∗.
sections.heading: 3.2 SWITCHING COST
sections.text: The concept of switching cost is used to quantify the adaptability of RL algorithms. The switching cost is defined as the number of policy changes of deployed policies in the running of the algorithm in K episodes, namely:
  Nswitch := K−1∑ k=1 I{πk 6= πk+1} (2)
  The goal of this paper is to equip algorithm with a criterion that learns π∗ using a few episodes while at the same time has small Nswitch.
  3.3 DEEP Q-LEARNING
  If we can estimate Q-function for each state and action pair well, there is no difficulty in finding π∗. For example, we can always select a∗ = arg maxaQ(x, a). However, it is not easy to learn Q value estimates for each state and action pair, especially when the state or the action space is large.
  In deep Q-learning (DQN), Mnih et al. (2015) combine deep networks and reinforcement learning successfully by using a deep neural network to approximate Q(x, a). Given the current state xh, the agent selects a action ah greedily based on the Q(xh, a), then the state move to xh+1 and a reward rt+1 is obtained. The transition (xt, at, rt+1, xt+1) is saved to the replay memory buffer. At each time, a batch of transitions is sampled from this buffer, and the parameters of neural networks are optimized by using stochastic gradient descent to minimize the loss
  (rh+1 + γh+1 max a′
  qθ̄(xh+1, a ′)− qθ(xh, ah))2 (3)
  where γh+1 is the chosen discount of time step h + 1, θ is the parameters of the online network, and θ̄ represents the parameters of the target network. The gradient of the loss is back-propagated
  only to update θ, while θ̄ is not optimized directly. DQN has been successful as it led to superhuman performance on several Atari games. Nevertheless, there are also several limitations of this algorithm and many extensions have been proposed. Rainbow (Hessel et al., 2018) combines six of these extensions and obtains an excellent and stable performance on many Atari games. In the Appendix A, we review these tricks. In this paper, we focus on Rainbow DQN with low switching cost.
sections.heading: 3.4 COUNT-BASED EXPLORATION
sections.text: In many real-world scenarios that require low switching cost, it is also required to use deterministic policies, especially in applications mentioned above. Exploring strategies like -greedy and noisy net make the policy stochastic, which we cannot use here. Count-based exploration algorithms are known to perform near-optimally when used in reinforcement learning for solving tabular MDPs. Tang et al. (2017) applied these algorithms into high-dimensional state spaces successfully. They discretized the state space with a hash function φ : S → Z. Then an exploration bonus r+(x) = β√ n(φ(x)) is added to the reward function and the agent is trained with the modified reward r + r+. Note that with the count-based exploration, the policy is deterministic.
sections.heading: 4 DETERMINISTIC RAINBOW DQN WITH A POLICY SWITCHING CRITERION
sections.text: In this section, we first introduce how to implement a deterministic Rainbow DQN with a policy switching criterion. This implementation combines six DQN tricks and the policy is always deterministic.
sections.heading: 4.1 DETERMINISTIC RAINBOW DQN
sections.text: We first discuss how to make Rainbow DQN always output deterministic policies. Recall that to explore more efficiently, Rainbow adopts the Noisy Net (Fortunato et al., 2018), which makes the policy stochastic. To obtain a deterministic policy and keep exploring, we remove Noisy Net and employ the Count-Based exploration described in the previous section. When the deployed policy interacts with the environment, it selects the action which maximizes theQ-function. After obtaining the reward by taking this action, an exploration bonus r+ = β√
  n(φ(x)) is added into the reward.
sections.heading: 4.2 DQN WITH A POLICY SWITCHING CRITERION
sections.text: Besides, Rainbow updates the policies which interacts with the environment directly. These policies usually switch millions of times during the training process (since the parameters are updated millions of times). In our implementation, we add an online policy in addition to the deployed policy that interacts with the environment. The deployed policy collects the data for the experience replay buffer, while the online policy is frequently updated when training. The deployed policy is replaced with the online policy when they meet the criterion we will discuss soon. The algorithm of deterministic switching Rainbow is shown in Algorithm 1.
sections.heading: 4.3 POLICY SWITCHING CRITERIA
sections.text: Here we first introduce two straightforward policy switching criteria.
  Fixed Interval Switching This is the simplest criterion, we switch the deployed policy with a fixed interval. Under the FIX n criterion, we switch the deployed policy whenever the online policy is updated n times where n is a per-specified number. We will specify n in our experiments.
  Adaptive Interval Switching This criterion aims to switch the deployed policy frequently at the first and reduce the switching speed gradually. Under the Adaptive n2m criterion, we increase the deployment interval from n to m. The interval between the i-th deployment and the (i + 1)-th deployment is min((i+ 1)× n,m). We will specify n and m in our experiments.
  Algorithm 1 Deterministic Switching Rainbow 1: Initialize arameters θonline, θdeployed, θtarget for online policy, deployed policy and target policy,
  initialize an empty replay buffer D 2: Denote the state encoder in online policy and deployed policy as fonline and fdeployed 3: Set the step to start training Hstart, the step to end training Hmax, and the interval to update the
  target policy Htarget. 4: Set n(accumulated updates) = 0, n(deployment) = 0 5: for h = 1 to Hmax do 6: Select ah = arg maxaQdeployed(sh, a) 7: Execute action at and observe reward rh and state xh+1 8: Compute the hash codes through for xh, φ(xh) = sgn(Ag(xh)) 9: . A is a fixed matrix with i.i.d. entries drawn from a standard Gaussian distributionN (0, 1)
  and g is a flat function 10: Update the hash table counts, n(φ(xh)) = n(φ(xh)) + 1 11: Update the reward rh = rh + β√
  n(φ(rh))
  12: Store (xh, ah, rh, xh+1) in D 13: if h > Hstart then 14: Sample a minibatch of transitions from D. 15: Update θonline by stochastic gradient descent on the sampled minibatch once. 16: if h % Htarget == 0 then 17: Update θtarget = θonline 18: Set n(accumulated updates) = n(accumulated updates) + 1 19: end if 20: if J (fdeployed, fonline, D, n(accumulated updates), n(deployment)) = true then 21: Update θdeployed = θonline 22: Update n(accumulated updates) = 0 23: Update n(deployment) = n(deployment) + 1 24: end if 25: end if 26: end for
  Algorithm 2 Switching Criteria (J in Algorithm 1) . Fixed interval switching FIX n input n(accumulated updates) output bool(n(accumulated updates) ≥ n)
  . Adaptive interval switching Adaptive n2m input n(accumulated updates), n(deployment) output bool(n(accumulated updates) ≥ min(n(deployment) + 1)× n,m)
  . Feature-based switching F a input fdeployed, fonline, D Sample minibatch B of transitions (xh) from D with probability ph Compute the the similarity sim(xh) =
  fdeployed(xh)·fonline(xh) ||fdeployed(xh)||×||fonline(xh)||
  Compute the average similarity in sampled batch sim(B) = ∑ x∈B sim(x) ||B|| output bool(sim(B) ≤ a)
  These two criteria and our proposed new criterion are summarized in Algorithm 2. Unfortunately, as will be shown in our experiments, these two criteria do not perform well. This requires us to design new principled criterion.
sections.heading: 5 FEATURE-BASED SWITCHING CRITERION
sections.text: In the section, we describe our new policy switching criterion based on feature learning. We first describe this criterion, and then we provide some theoretical justification from a representation learning point of view.
  Feature-based Switching Criterion We adopt the view the DQN learns to extract informative features of the states of environments. Our proposed criterion tries to switch the deployed policy according to the extracted feature. When deciding whether to switch the deployed policy or not, we first sample a batch of states B from the experience replay buffer, and then extract the feature of all states by both the deployed deep Q-network and online deep Q-network.
  For a state x, the extracted feature are denoted as fdeployed(x) and fonline(x), respectively. The similarity score between fdeployed and fonline on state x is defined as
  sim(x) = 〈fdeployed(x), fonline(x)〉
  ||fdeployed(x)|| × ||fonline(x)||
  We then compute the averaged similarity score on the batch of states B sim(B) = ∑ x∈B sim(x)
  ||B||
  With a hyper-parameter a ∈ [0, 1], the feature-based policy switching criterion is to change the deployed policy whenever sim(B) ≤ a.
  Theoretical Justification Our criterion is inspired by representation learning. To illustrate the idea, we consider the following setting. Suppose we want to learn f(·), a representation function that maps the input to a k-dimension vector. We assume we have input-output pairs (x, y) with y = 〈w, f∗(x)〉 for some underlying representation function f∗(·) and a linear predictor w ∈ Rk. For ease of presentation, let us assume we know w, and our goal is to learn the underlying representation which together with w gives us 0 prediction error.
  Suppose we have data sets D1 and D2. We use D1 to train an estimator of f∗, denoted as f1, and D1 ∪ D2 to train another estimator of f∗, denoted as f1+2. The training method is empirical risk minimization, i.e.,
  f1 ← min f∈F
  1 |D1| ∑
  (x,y)∈D1
  (y − 〈w, f(x)〉)2 and f1+2 ← min f∈F
  1 |D1 ∪ D2| ∑
  (x,y)∈D1∪D2
  (y − 〈w, f(x)〉)2
  where F is some pre-specified representation function class. The following theorem suggests if the similarity score between f1 and f1+2 is small, then f1 is also far from the underlying representation f∗. Theorem 1. Suppose f1 and f1+2 are trained via aforementioned scheme. There exist dataset D1, D2, function classF andw such that if the similarity score between f1 and f1+2 onD1+2 is smaller than α, then the prediction error of f1 on D1+2 is 1− α.
  The proof is deferred to Appendix B where we give explicitly constructions.
  Theorem 1 suggests that in certain scenarios, if the learned representation has not converged (the similarity score is small), then it cannot be the optimal representation which in turn will hurt the prediction accuracy. Therefore, if we find the similarity score is small, we should change the deployed policy.
sections.heading: 6 EXPERIMENTS
sections.text: In this section, we conduct experiments to evaluate different policy switching criteria on DQN. We study several Atari game environments along and an environment for simulating sepsis treatment for ICU patients. We evaluate the efficiency among different switching criteria in these environments. Implementation details and hyper-parameters are listed in the Appendix A.
sections.heading: 6.1 ENVIRONMENTS
sections.text: GYMIC GYMIC is an OpenAI gym environment for simulating sepsis treatment for ICU patients to an infection, where sepsis is caused by the body’s response to an infection and could be lifethreatening. GYMIC built an environment to simulate the MIMIC sepsis cohort, where MIMIC is an open patient EHR dataset from ICU patients. This environment generates a sparse reward, the reward is set to +15 if the patient recovered and -15 if the patient died. This environment has 46 clinical features and a 5 × 5 action space. For the GYMIC, we display the learning curve of 1.5 million steps of the environment, after which the reward converge. We choose this environment because it is simulating a real-world problem that requires low switching cost. For Atari games, all the experiments were training for the environment stepping 3.5 million times.
  Atari 2600 Atari 2600 games are widely employed to evaluate the performance of DQN based agents. We also evaluate the efficiency among different switching criteria on several games, such as Pong, Road Runner, Beam Rider, etc.
sections.heading: 6.2 RESULTS AND DISCUSSIONS
sections.text: For all environments, we evaluate a feature-based criterion F 0.98, three fixed interval criteria covering a vast range FIX 102, F IX 103 and FIX 104, and an adaptive criterion increasing the deploying interval from 100 to 10,000. Besides the switching criteria we discussed above, we use “None” to indicate an experiment without the low-switching-cost constraint where deployed policy kept in sync with online policy all the time, notice that this experiment is equivalent to FIX 1.
  Riverraid, although FIX 104 and Adaptive lead to lower switching cost, they fail to learn how to play the games well. Therefore, they are not desired generic policy switching criterion.
  Secondly, we observe that changing the policy with an adaptive interval may be better than a fixed interval. Focusing on the criteria FIX 104 andAdaptive 102to104, the adaptive criterion switches the online policy fast at first and decrease its switching speed gradually, and in the end, the adaptive criterion would have the same speed as the fixed one. Therefore, there is no significant difference
  between the total switching cost of these two criteria. However, we could observe that the adaptive criterion’s performance is better than the fixed one when playing Beam Rider, Pong, Qbert, and they obtain similar performances in the rest games.
  Lastly, we find our proposed feature-based criterion (F 0.98) is the desired on that satisfy all four properties we discussed in Section 1. It significantly reduces the switching cost compared to “None”, and is smaller than FIX 102. While it incurs higher switching cost than FIX 103, FIX 104, and Adaptive 102to104, on all environments feature-based criterion consistently perform as well as “None” in the sense that 1) it finds the optimal policy eventually, 2) it has the same sample efficiency as “None”. On the other hand, other criteria sometime have significantly worse performance compared to “None”, so none of them is a generic solution.
sections.heading: 7 CONCLUSION
sections.text: In this paper, we focus on the concept of switching cost and take a step toward designing a generic solution for reducing the switching cost while maintaining the performance. Inspired by representation learning theory, we proposed a new feature-based policy switching criterion for deep Q-learning methods. Through experiment on one medical simulation environment and six Atari games, we find our proposed criterion significantly reduces the switching cost and at the same time enjoys the same performance as the case where there is no switching cost constraint.
  We believe our paper is just the first step on this important problem. One interesting question is how to design principled policy switching criteria for policy-based and model-based methods. Another direction is to give provable guarantees for these policy switching criteria that work for methods dealing with large state space in contrast to existing analyses are all about tabular RL (Bai et al., 2019; Zhang et al., 2020b;a).
sections.heading: A DETAILS OF EXPERIMENTS
sections.text: A.1 DETAILED ALGORITHM
  For completeness, we introduce the extensions of DQN and display our detailed algorithm.
  Double Q-learning Conventional Q-learning is affected by an overestimation bias, due to the maximization step in Equation 3, Double Q-learning (Hasselt et al., 2016) address this problem by decoupling. They use the loss
  (rh+1 + γh+1qθ̄(xh+1, arg max a′
  qθ(xh+1, a ′))− qθ(xh, ah))2 (4)
  This change reduce harmful overestimations that were present for DQN, which leads to a improvement.
  Multi-step learning Q-learning accumulates a single reward, Sutton (2005) use a forward-view multi-step accumulated reward long ago, where a n-step accumulated reward is defined as
  r (n) h := n−1∑ k=0 γ (n) h rh+k+1 (5)
  and the final loss is (r
  (n) h + γ (n) h maxa′ qθ̄(xh+1, a ′)− qθ(xh, ah))2 (6)
  Multi-step targets often lead to faster learning (Sutton & Barto, 2005)
  Dueling networks Wang et al. (2016) splits the DQN network into two streams called value stream V and advantage stream A, these two strems share the convolutional encoder f , and action value Q(x, a) could be computed as:
  Q(x, a) = V (f(x)) +A(f(x), a)− ∑ a′ A(f(x), a ′)
  Nactions (7)
  Prioritized replay DQN samples uniformly from the replay buffer, to sample more frequently from those transitions from which the policy can learn more and quickly, Schaul et al. (2016) samples transitions with probability ph relative to the last encountered absolute TD error
  ph ∝ |rh+1 + γh+1 max a′ qθ̄(xh+1, a ′)− qθ(xh, ah)|ω (8)
  where ω is a hyper-parameter, and new transitions always have the maximum priority when they enter the buffer to ensure a bias towards unseen transitions.
  Distributional RL Instead of approximating the expected return as DQN, Bellemare et al. (2017) proposed a method to approximate the distribution of returns on a a discrete support z, z is a vector with Natoms atoms and is defined as
  zi = Vmin + (i− 1) Vmax − Vmin Natoms − 1 , i ∈ 1, 2, ..., Natoms (9)
  where Vmin and Vmax is the minimal and maximal value in this support. The approximating distribution dh is defined on this support and the probability piθ(xh, ah) on each atom i as dh = (z, pθ(xh, ah)) .The goal is to update the trainable parameters θ to match this distribution with the actual distribution of returns. To learn the probability piθ for each i with a variant of Bellman’s equation, they minimize the Kullbeck-Leibler divergence DKL(Φzd′h||dh) between the distribution dh and the target distribution d′h := (rh+1+γh+1z, pθ̄(xh+1, arg maxa′ qθ̄(xh+1, a
  ′))), where Φz is a L2-projection from the target distribution to the fixed support z and qθ̄(xh+1, a) = z T pθ̄(xh+1, a)
  Nosiy Net To address the limitations of exploring using -greedy policies, Fortunato et al. (2018) propose a noisy linear layer
  y = b+Wx+ (bnoisy b + (Wnoisy w)x) (10) to replace the standard linear y = b + Wx, where b and w are random variables, denotes the element-wise product.
  Rainbow combines all of these 6 extensions, To make the policy deterministic but still keep exploring during training, we remove the Noisy Net and adopt Count-Based exploration. The detailed algorithm is as follows.
  Algorithm 3 Detailed algorithm 1: . Hyper-parameters for extensions 2: Distributional RL: Number of atoms Natoms, min/max values Vmin/Vmax 3: Prioritization replay memory: exponent ω, capacity N 4: Multi-step: number of steps n 5: . Initialization 6: Initialize prioritization replay memory D, state encoder fonline, value stream Vonline and advan-
  tage stream Aonline for online policy Ponline 7: Initialize deployed policy Pdeployed and target policy Ptarget with parameters in Ponline 8: . Definition of Q-function 9: zi = Vmin + (i− 1) vmax−vminNatoms−1
  10: Āionline(x) = 1
  Nactions
  ∑ aA i online(fonline(x), a)
  11: pionline(x, a) = softmax(V i online(fonline(x)) +A i online(fonline(x), a)− Āionline(x)) 12: Qonline(x, a) = ∑ i zip i online(x, a)
  13: Similarly, Qdeployed(x, a) = ∑ i zip i deployed(x, a), Qtarget(x, a) = ∑ i zip i target(x, a) 14: 15: . Training process 16: set up environment 17: n(accumulated updates) = 0, n(deployment) = 0 18: for h = 1 to Hmax do 19: if Termination then 20: reset environment 21: end if 22: select ah = arg maxaQdeployed(xh, a) 23: Execute action ah in emulator and observe reward rh and state xh+1 24: compute the hash codes through for xh, φ(xh) = sgn(Ag(xh)) 25: . A is a matrix with i.i.d. entries drawn from a standard Gaussian distribution N (0, 1) and
  g is a flat function 26: update the hash table counts, n(φ(xh)) = n(φ(xh)) + 1 27: update the reward rh = rh + β√
  n(φ(xh))
  28: store (xh, ah, rh, xh+1) in D 29: if h > Hstart then 30: sample minibatch of transitions (xh′ , ah′ , wh′ , rh′ , rh′+1 ..., rh′+n−1, xh′+n) from D
  with probability ph′ 31: . wh′ is the importance-sampling weight for transitions at h′
  32: compute the multi-step reward r(n)h′ = ∑n−1 k=0 γ
  nrh′+k 33: a∗ = arg maxaQonline(xh′+n, a),mi = 0, i ∈ 1, 2, ..., Natoms 34: for j = 1 to Natoms do 35: T̂ zj = [r(n)h′ + γnzj ].clip(Vmin, Vmax) 36: ∆z = (Vmax − Vmin)/(Natoms − 1) 37: bj = (T̂ zj − Vmin)/∆z, l = bbjc, u = dbje 38: ml = ml + p j target(xh′+n, a
  ∗)(u− bj),mu = mu + pjtarget(xh′+n, a∗)(bj − l) 39: end for 40: DKLh′ = − ∑ imi log p i online(xh′ , ah′) 41: update ph′ by ||DKLh′ ||ω 42: update parameters in Ponline by a gradient descent step on DKLh′ × wh′
  43: n(accumulated updates) = n(accumulated updates) + 1 44: if h % Htarget then 45: update Ptarget by the parameters of Ponline 46: end if 47: if J (fd, fo, D, n(accumulated updates),n(deployment)) = true then 48: update Pdeployed by the parameters of Ponline 49: n(accumulated updates) = 0, n(deployment) = n(deployment) + 1 50: end if 51: end if 52: end for
  A.2 HYPE-PARAMETERS
  Table 1 lists the basic hyper-parameters of the algorithm, all of our experiments share these hyperparameters except the experiments on GYMIC adopt the Htarget as 1K. Most of these parameter are the same with raw Rainbow algorithm. For the count base exploration, the bonus is β set to 0.01.
  Table 2 lists the rest hyper-parameters for experiments on GYMIC. Since there are 46 clinical features in this environment, we stack 4 consecutive states to compose a 184-dimensional vector as the input for the state encoder fonline(fdeployed or ftarget). The state encoder is a 2-layer MLP with hidden size 128.
  Table 3 shows the additional hyper-parameters for experiments on Atari games. The observations are grey-scaled and resized to 84× 84 tensor, and 4 consecutive frames are concatenated as a single state, each action selected by the agent is repeated for 4 times. The state encoder is composed of 3 convolutional layers with 32, 64 and 64 channels, which use 8x8, 4x4, 3x3 filters and strides of 4, 2, 1 respectively.
  A.3 REWARD AND SWITCHING COST
  In the end, we list the value of the switching cost and reward of different criteria when the environment take 1.5 million steps and 3 million steps in Table 4.
sections.heading: B PROOF FOR SECTION 5
sections.text: Proof of Theorem 1. We let w = (1, 1, . . . , 1) ∈ Rk be a k-dimensional all one vector. We let
  F = {f : f(x) = (2σ(〈v1, x〉)− 1, 2σ(〈v2, x〉)− 1, . . . , 2σ(〈vk, x〉)− 1)} ⊂ {Rk → Rk}
  with σ(·) being the ReLU activation function1 and vi ∈ {ei,−ei} where ei ∈ Rk denotes the vector that only the i-th coordinate is 1 and others are 0. We assume k is an even number and αk is an integer for simplicity. We let the underlying f∗ be the vector correspond to (e1, e2, . . . , ek). We let D1 = {(e1, 1), (e2, 1), . . . , (e(1−α)k, 1)} and D2 = {(e(1−α)k+1, 1), . . . , (ek, 1)}. Because we use the ERM training scheme, it is clear that the training on D1 ∪ D2 will recover f∗, i.e., f1+2 = f∗ because if it is not f∗ is better solution (f∗ has 0 error ) for the empirical risk. Now if the similarity score between f1 and f1+2 is smaller than α, it means for f1, its corresponding {v(1−α)k+1, . . . , vk} are not correct. In this case, f1’s prediction error is at least 1−α onD1∪D2, because it will predict 0 on all inputs of D2.
  1We define σ(0) = 0.5
  1, 50
  0, 00
  0 st
  ep s
  en vi
  ro nm
  en t
  cr ite
  ri a
  N on
  e FI
  X 1 02
  FI X
  1 0
  3 FI
  X 1 0
  4 A
  da pt
  iv e
  F 0.
  98
  ba ttl
  e zo
  ne Sw
  itc hi
  ng co
  st 36
  87 50
  .0 36
  87 .5
  36 9.
  0 36
  .5 84
  .5 52
  9. 2
  R ew
  ar d
  26 90
  0 .0 ±
  94 45 .1
  2 3 0 7 0.
  0 ±
  7 6 9 1 .9
  1 7 9 3 0 .0 ±
  4 4 7 2.
  7 1 8 8 7 0 .0 ±
  4 4 1 7.
  4 1 4 3 3 0 .0 ±
  4 3 9 7.
  9 1 6 9 7 0 .0 ±
  5 7 6 6. 2 G ap N /A -3 83 0. 0 -8 97 0. 0 -8 03 0. 0 -1 25 70 .0 -9 93 0. 0
  be am
  ri de
  r Sw
  itc hi
  ng co
  st 36
  87 50
  .0 36
  87 .5
  36 9.
  0 36
  .5 84
  .5 11
  9. 6
  R ew
  ar d
  76 55 .9 ±
  20 21 .2
  7 5 5 4.
  2 6 ±
  2 2 8 3 .4
  7 4 9 3.
  7 6 ±
  2 3 7 6.
  4 4 0 6 8.
  2 6 ±
  1 3 4 0.
  2 4 0 7 8.
  5 6 ±
  1 8 1 9.
  8 6 7 5 9.
  7 4 ±
  2 1 3 6. 3 G ap N /A -1 01 .6 -1 62 .1 -3 58 7. 6 -3 57 7. 3 -8 96 .2
  po ng
  Sw itc
  hi ng
  co st
  36 87
  50 .0
  36 87
  .5 36
  9. 0
  36 .5
  84 .5
  16 81 .4 R ew ar d − 12 .8 7 ± 8. 1 − 2. 5 ± 9 .2 − 1 3. 6 9 ± 4. 0 − 1 2. 9 7 ± 5. 2 − 7. 1 4 ± 1 0. 2 0. 0 8 ±
  6. 7
  G ap
  N /A
  10 .4
  -0 .8
  -0 .1
  5. 7
  12 .9
  qb er
  t Sw
  itc hi
  ng co
  st 36
  87 50
  .0 36
  87 .5
  36 9.
  0 36
  .5 84
  .5 12
  68 .5
  R ew
  ar d
  60 50 .2
  5 ±
  21 89 .2
  5 0 7 3 .7
  5 ±
  6 2 4 .7
  4 3 5 9.
  7 5 ±
  5 3 4 .2
  6 4 9 .2
  5 ±
  2 4 5 .3
  2 6 8 1.
  0 ±
  1 6 9 6 .1
  3 9 4 7.
  5 ±
  1 4 3 8. 0 G ap N /A -9 76 .5 -1 69 0. 5 -5 40 1. 0 -3 36 9. 2 -2 10 2. 8
  riv er
  ra id
  Sw itc
  hi ng
  co st
  36 87
  50 .0
  36 87
  .5 36
  9. 0
  36 .5
  84 .5
  89 9. 5 R ew ar d 54 53 .2 ± 78 7 .6 4 6 0 2. 8 ± 6 9 3 .8 4 1 7 7 .0 ± 8 7 0 .0 3 1 5 2 .6 ± 6 5 8 .6 3 2 6 7 .6 ± 7 0 5 .2 4 1 8 2 .2 ±
  9 2 5 .8
  G ap
  N /A
  -8 50
  .4 -1
  27 6.
  2 -2
  30 0.
  6 -2
  18 5.
  6 -1
  27 1.
  0
  ro ad
  ru nn
  er Sw
  itc hi
  ng co
  st 36
  87 50
  .0 36
  87 .5
  36 9.
  0 36
  .5 84
  .5 13
  09 .0
  R ew
  ar d
  13 26
  6 .0 ±
  15 13 .4
  2 6 0 3 9.
  0 ±
  4 6 0 5 .4
  1 4 9 4 7 .0 ±
  2 0 0 0.
  3 3 0 6 2 0 .0 ±
  6 9 4 6.
  2 1 9 5 1 3 .0 ±
  4 7 5 1.
  0 2 8 9 6 8 .0 ±
  4 8 2 7. 2 G ap N /A 12 77 3. 0 16 81 .0 17 35 4. 0 62 47 .0 15 70 2. 0 3, 00 0, 00 0 st ep s
  ba ttl
  e zo
  ne Sw
  itc hi
  ng co
  st 74
  37 50
  .0 74
  37 .5
  74 4.
  0 73
  .5 12
  2. 5
  42 40 .3 R ew ar d 32 25 0 .0 ± 81 19 .6 2 3 9 1 0. 0 ± 6 2 8 9 .8 2 1 2 9 0 .0 ± 8 1 9 1. 8 1 7 8 3 0 .0 ± 4 3 8 4. 2 1 2 5 3 0 .0 ± 5 0 9 6. 0 2 6 1 8 0 .0 ±
  7 1 6 1. 5 G ap N /A -8 34 0. 0 -1 09 60 .0 -1 44 20 .0 -1 97 20 .0 -6 07 0. 0
  be am
  ri de
  r Sw
  itc hi
  ng co
  st 74
  37 50
  .0 74
  37 .5
  74 4.
  0 73
  .5 12
  2. 5
  12 33 .4 R ew ar d 13 75 1 .2 ± 65 30 .9 1 1 3 9 3 .2 4 ± 4 8 0 2. 1 1 2 2 3 6 .6 2 ± 5 6 6 9. 9 5 6 5 4. 1 6 ± 2 1 2 0. 0 8 8 5 7. 9 4 ± 3 1 7 3. 9 1 2 3 1 1 .3 4 ±
  6 7 3 1 .4
  G ap
  N /A
  -2 35
  8. 0
  -1 51
  4. 6
  -8 09
  7. 0
  -4 89
  3. 3
  -1 43
  9. 9
  po ng
  Sw itc
  hi ng
  co st
  74 37
  50 .0
  74 37
  .5 74
  4. 0
  73 .5
  12 2.
  5 26
  87 .0
  R ew
  ar d
  17 .9
  6 ±
  6. 8
  1 7 .9
  2 ±
  4. 4
  2 0 .3
  5 ±
  2. 3
  1 7 .0 ±
  5. 0
  1 9 .0
  2 ±
  2. 2
  1 7 .4
  3 ±
  5 .4
  G ap
  N /A
  -0 .0
  2. 4
  -1 .0
  1. 1
  -0 .5
  qb er
  t Sw
  itc hi
  ng co
  st 74
  37 50
  .0 74
  37 .5
  74 4.
  0 73
  .5 12
  2. 5
  19 80 .5 R ew ar d 17 68 5 .2 5 ± 24 86 .0 1 7 0 3 8. 5 ± 2 7 1 0 .1 1 3 8 3 6 .0 ± 4 0 3 2. 8 2 1 9 3. 7 5 ± 1 6 2 9. 5 3 8 3 8. 0 ± 1 7 1 6 .6 1 3 7 9 1 .0 ±
  3 3 7 2. 0 G ap N /A -6 46 .8 -3 84 9. 2 -1 54 91 .5 -1 38 47 .2 -3 89 4. 2
  riv er
  ra id
  Sw itc
  hi ng
  co st
  74 37
  50 .0
  74 37
  .5 74
  4. 0
  73 .5
  12 2.
  5 23
  25 .5
  R ew
  ar d
  78 08 .6 ±
  30 8 .6
  7 8 4 0.
  3 ±
  3 5 1 .4
  7 8 7 2 .9 ±
  9 3 9 .1
  3 3 9 1 .1 ±
  8 2 1 .2
  4 0 1 3 .5 ±
  9 3 8 .3
  7 0 5 2 .3 ±
  8 6 2 .7
  G ap
  N /A
  31 .7
  64 .3
  -4 41
  7. 5
  -3 79
  5. 1
  -7 56
  .3
  ro ad
  ru nn
  er Sw
  itc hi
  ng co
  st 74
  37 50
  .0 74
  37 .5
  74 4.
  0 73
  .5 12
  2. 5
  27 36 .6 R ew ar d 37 48 0 .0 ± 84 29 .9 3 6 1 1 8. 0 ± 6 3 6 6 .6 3 6 7 2 2 .0 ± 7 1 1 9. 7 3 5 0 5 5 .0 ± 7 0 9 5. 8 4 5 7 0 6 .0 ± 8 4 7 3. 7 4 5 9 4 0 .0 ±
  8 2 3 4. 1 G ap N /A -1 36 2. 0 -7 58 .0 -2 42 5. 0 82 26 .0 84 60 .0
  Ta bl
  e 4:
  W e
  lis t
  th e
  va lu
  e of
  th e
  sw itc
  hi ng
  co st
  an d
  re w
  ar d
  of di
  ff er
  en t
  cr ite
  ri a
  w he
  n th
  e en
  vi ro
  nm en
  t ta
  ke s
  1. 5
  m ill
  io n
  st ep
  s an
  d 3
  m ill
  io n
  st ep
  s. “R
  ew ar d” co rr es po nd s to th e ab so lu te va lu e of th e re w ar d, an d “G ap ” de no te s th e di ff er en ce be tw ee n th e re w ar d un de ra sp ec ifi c cr ite ri on an d “N on e. ” A nd “S w itc hi ng C os t” co rr es po nd s to th e sw itc hi ng co st un de ra cr ite ri on at th is tim e st ep .