ExTra: Transfer-guided Exploration
Anirban Santara Rishabh Madan Balaraman Ravindran Pabitra Mitra


Equal contribution by A. Santara and R. Madan. R. Madan worked on this project while he was a student at Indian Institute of Technology Kharagpur. A. Santara is currently working at Google Research.
Published as an Extended Abstract.




 Indian Institute of Technology Kharagpur
 Kharagpur 
 WB, India

nrbnsntr@gmail.com



 University of Washington
 Seattle 
 Washington

rishabhmadan96@gmail.com



 Indian Institute of Technology Kharagpur
 Kharagpur 
 WB, India

pabitra@cse.iitkgp.ernet.in



 Indian Institute of Technology Madras
 Chennai 
 TN, India

ravi@cse.iitm.ac.in


  
In this work we present a novel approach for transfer-guided exploration in reinforcement learning that is inspired by the human tendency to leverage experiences from similar encounters in the past while navigating a new task. Given an optimal policy in a related task-environment, we show that its bisimulation distance from the current task-environment gives a lower bound on the optimal advantage of state-action pairs in the current task-environment. Transfer-guided Exploration (ExTra) samples actions from a Softmax distribution over these lower bounds. In this way, actions with potentially higher optimum advantage are sampled more frequently. In our experiments on gridworld environments, we demonstrate that given access to an optimal policy in a related task-environment, ExTra can outperform popular domain-specific exploration strategies viz. epsilon greedy, Model-Based Interval Estimation – Exploration Bonus (MBIE-EB), Pursuit and Boltzmann in rate of convergence. We further show that ExTra is robust to choices of source task and shows a graceful degradation of performance as the dissimilarity of the source task increases. We also demonstrate that ExTra, when used alongside traditional exploration algorithms, improves their rate of convergence. Thus it is capable of complementing the efficacy of traditional exploration algorithms.

  

ExTra: Transfer-guided Exploration 
    Balaraman Ravindran
    Submitted: 28 June 2019
 Revised: 20 August 2019
====================================================



§ INTRODUCTION

While attempting to solve a new task human beings tend to take actions motivated by similar situations faced in the past. 
These actions often happen to be good starting points even if the prior experiences are not in the exact same task-environment. A Reinforcement Learning (RL) agent learns by trial and error in an environment using reward signals that are indicative of progress or accomplishment of the target task <cit.>. The agent uses two policies to act in the environment during the learning phase. The policy that the agent learns to exploit for solving the target task is known as the target policy. The agent also has a behavioral policy that it uses for exploration in order to find better solutions for the target policy. The sample efficiency and convergence time of an RL algorithm heavily depends on the exploration method used by the behavioral policy. A large body of research in reinforcement learning has been dedicated to the formulation of sample-efficient algorithms. Some of the notable developments include count based exploration <cit.>, curiosity driven exploration <cit.>, optimism in the face of uncertainty <cit.>, Thompson sampling or posterior sampling and bootstrapped methods <cit.>, parameter space exploration <cit.> and intrinsic motivation <cit.>. However these methods are based on heuristics specific to the current environment and do not use any prior experiences of the agent in other environments.
 


The motivation of this work is to formulate an exploration method that uses prior experiences of an agent at similar tasks in other environments for improving the efficiency of exploration in the current task-environment. Prior work includes learning action priors from one or more source tasks to identify useful actions or affordances for the target task <cit.>, policy and value function initialization <cit.>, policy reuse <cit.>, policy transfer through reward shaping <cit.> and transfer of samples <cit.>. Recent work in the Meta Reinforcement Learning community have approached this problem from the perspectives of representation learning  <cit.> and introduction of structured stochasticity via a learned latent space <cit.>. However most of these methods are limited to using source tasks that share the same state and action spaces as the target task. In this paper, we consider the more general setting of cross-domain transfer where the source environment can have different state and action spaces. Cross-domain transfer in RL has been studied by <cit.> and <cit.> who propose methods involving transfer of rules and adaptation of the source policy respectively. We take a different approach in our paper that is based on the theory of bisimulation based policy transfer <cit.>. Bisimulation metric measures the distance between states in terms of their long term behavior. Bisimulation and its close analogue MDP Homomorphism <cit.> have been extensively used for transfer learning in RL <cit.> and provide strong theoretical performance guarantees. 





Given a source environment with a known optimal policy for a related task and its lax-bisimulation distance function <cit.> from the current task-environment, we derive a lower bound on the optimal advantage of state-action pairs of the current environment. During exploration in the current environment, the agent samples actions from a Softmax distribution over these lower bounds. Thus we use transfer learning to guide the exploration in a way that actions with potentially higher advantage are chosen with higher probability. We call this algorithm Transfer-guided Exploration, abbreviated as ExTra. Our experiments demonstrate that ExTra can achieve significant gains in rate of convergence of Q-learning over exploration methods that only use information associated to the current environment.




Our contributions in this paper can be summarized as follows:

    
  * We prove that transfer via bisimulation <cit.> maximizes a lower bound on the optimal advantage of target actions.
    
  * We use this bisimulation distance based lower bound to formulate the Transfer-guided Exploration (ExTra) algorithm as a means of using prior experiences for accelerating reinforcement learning in new environments.
    
  * We demonstrate that given the optimal policy from a related task-environment and its lax-bisimulation distance function, ExTra achieves faster convergence compared to exploration methods that only use local information. Additionally, ExTra is robust to source task selection with predictable graceful degradation of performance and can complement traditional exploration methods by improving their rates of convergence.


The rest of the paper is organized as follows. We briefly describe the essential theoretical concepts used in this paper in Section <ref>. Then we introduce ExTra in Section <ref> and present the results of comparison with traditional exploration methods in Section <ref>. We conclude the paper with a summary of the proposed method and scope of future work in Section <ref>.


§ BACKGROUND


In this section we present a brief introduction to the essential theoretical concepts used in this paper. A Markov Decision Process (MDP) is a discrete time stochastic control process that is commonly used as a framework for reinforcement learning <cit.>. An MDP is defined as ℳ = ⟨ S, A, P, R ⟩ where S is the set of states of the environment, A is the set of actions available to the agent, P : S × A × S → [0, 1] is the transition function that gives a probability distribution over next states for each state, action pair and R : S× A →ℝ is the reward function for the task at hand. 
A policy is defined as a function π:S → A that returns an action for a given state. When an agent executes a policy π, it generates a trajectory τ = ⟨ s_1, a_1, s_2, a_2, …, s_T ⟩ and the 
accumulated reward obtained in the trajectory is written as ℛ(τ|π). The goal of RL is to find the optimal policy π^* that maximizes the expectation of ℛ(τ|π).

    π^* = argmax_π𝔼_τ∼π[ℛ(τ|π)]


The state action value function Q^π(s, a) of a policy π is defined as the expected cumulative reward that an agent can get by starting at a state s, taking action a and henceforth following the policy π. 



The optimum state-action value function Q^*(s,a) is defined as Q^*(s,a) = max_πQ^π(s,a)   ∀ s∈ S, a ∈ A and the optimal policy π^* can be written in terms of Q^*(s,a) as:

    π^*(s) = argmax_a∈ A Q^*(s,a)

The optimal value function, Q^*(s,a) can be obtained by value iteration using the Bellman equation <cit.>:

    Q^t+1(s,a) = ∑_s' P(s, a, s') (R(s, a) + γmax_b Q^t(s',b))

As t→∞, Q^t(s,a) → Q^*(s,a). 
We use value iteration to obtain the optimal policies in all our experiments in this paper. In the next two subsections we introduce exploration and transfer methods in RL.



 §.§ Exploration in Reinforcement Learning

A reinforcement learning agent learns through trial and error in the environment. At any step of decision making, the agent either "exploits" the best policy it has learned or "explores" other actions in search of a better strategy. Balancing exploration and exploitation is a key challenge in RL 
and a large body of literature has been dedicated to the formulation of strategies that address this dilemma. Exploration strategies can be widely classified into two categories: directed and undirected <cit.>. While directed exploration methods utilize exploration specific knowledge collected online, undirected exploration methods are driven almost purely by randomness with the occasional usage of estimates of utility of a state-action pair <cit.>. Popular undirected exploration algorithms include random walk <cit.>, ϵ-greedy <cit.> and softmax or Boltzmann exploration <cit.>. On the other hand, some notable directed exploration methods are count-based <cit.>, error-based  <cit.>, and recency based <cit.>. In the rest of this section, we briefly describe the exploration algorithms that are used as baselines in the current work. For a detailed review of exploration algorithms in RL, please refer to <cit.>.



  §.§.§ ϵ-greedy
 In epsilon-greedy exploration, the agent explores by choosing random actions with probability ϵ and follows the learned policy greedily the rest of the time.



  §.§.§ Model Based Interval Estimation - Exploration Bonus (MBIE-EB)
 MBIE-EB <cit.> is a count-based exploration algorithm that supplies the agent with count-based reward bonuses for favouring exploration of less visited states and actions. The reward bonus is calculated as:

    r_bonus(s,a) = β/√(n(s,a))

where n(s,a) is the number of times the agent chose the state action pair (s,a).



  §.§.§ Pursuit

Pursuit <cit.> is an undirected exploration algorithm for Multi-Arm Bandits, adapted for MDP by <cit.>. In Pursuit, the agent follows a stochastic policy π(s,a). 
After the update step, t, if a^*_t+1 = argmax_a Q_t+1(s_t, a), Pursuit updates π_t+1(s_t, a) as follows:


    π_t+1(s_t, a) =
            π_t(s_t, a) + β [1 - π_t(s_t, a)],      if  a = a^*_t+1
    π_t(s_t, a) + β [0 - π_t(s_t, a)],      if  a  a^*_t+1

where β is a hyperparameter.



  §.§.§ Boltzmann exploration

Boltzmann or Softmax exploration <cit.> is another undirected exploration algorithm in which 
the probabilities of the different actions are assigned by a Boltzmann distribution over 
the state-action value function Q_t(s_t,a).

    π(s_t,a) = e^Q_t(s_t,a)/T/∑_i=1^m e^Q_t(s_t, a^i)/T




 §.§ Transfer in Reinforcement Learning

Transfer learning aims to achieve generalization of skills across tasks by using knowledge gained in one task to accelerate learning of a different task. In reinforcement learning, the transferred knowledge can be high level, such as, rules or advice, sub-task definitions, shaping reward, or low level, such as, task features, experience instances, task models, policies, value functions and distribution priors. Most transfer algorithms for RL make certain assumptions about the relationship between the source and target MDPs. Taylor et al. <cit.> gives a comprehensive overview. In this work, we study the general case of transfer of knowledge between MDPs with discrete state and action spaces and make no assumptions about their structures or relationship. We use the bisimulation transfer framework of <cit.> as it provides a principled method of transfer for the general setting and a way to estimate the relative goodness of actions under the transferred model <cit.>.



 §.§ Transfer using bisimulation metric


Bisimulation, first introduced for MDP by Givan et al. <cit.>, is a relation that draws equivalence between states of an MDP that have the same long-term behavior. Bisimulation is equivalent to the theory of MDP homomorphism <cit.> that studies equivalence relations based on reward structure and transition dynamics. For an MDP, ℳ = ⟨ S, A, P, R ⟩, a relation E⊂ S × S is a bisimulation relation if, for s_1, s_2 ∈ S, whenever s_1 E s_2, the following conditions hold:

    ∀ a∈ A,   R(s_1, a)    =    R(s_2, a)
    ∀ a∈ A, ∀ C ∈ S/E,  ∑_s'∈ C P(s_1, a)(s')    =   ∑_s'∈ C P(s_2, a)(s')


S/E is the set of equivalence classes induced by E in S. Ferns et al. <cit.> proposed bisimulation metric as a quantitative analogue of the bisimulation relation that can be used as a notion of distance between states of an MDP. Under this metric, two states are bisimilar if their bisimulation distance is zero. The higher the distance, the more dissimilar the states are. In order  to measure the bisimulation distance between state-action pairs of different MDPs, Taylor et al. <cit.> introduced the lax bisimulation metric. Considering two MDPs, ℳ_1 = ⟨ S_1, A_1, P_1, R_1 ⟩ and ℳ_2 = ⟨ S_2, A_2, P_2, R_2 ⟩ the lax bisimulation metric is defined as follows.



Lax bisimulation metric <cit.>: Let M be the set of all semi-metrics on S_1 × A_1 × S_2 × A_2. ∀ s_1∈ S_1, a_1∈ A_1, s_2∈ S_2, a_2∈ A_2, d∈ M, F:M→ M is defined as:

    F(d)(s_1, a_1, s_2, a_2) = c_R |R_1(s_1, a_1)-R_2(s_2, a_2)| +
         c_T T_K(d')(P_1(s_1, a_1), P_2(s_2, a_2))


Where d'(s_1, s_2) = max(max_a_1∈ A_1min_a_2∈ A_2 d((s_1, a_1), (s_2, a_2)), 
min_a_1∈ A_1max_a_2∈ A_2 d((s_1, a_1), (s_2, a_2))) and T_K(d')(P_1(s_1, a_1),
 P_2(s_2, a_2)) is the Kantorovich distance <cit.> between the transition probability distributions. c_R, c_T ∈ℝ are  tunable hyperparameters representing relative weightages for the reward and Kantorovich components. F has a least-fixed point d_L and d_L is called the Lax Bisimulation Metric between ℳ_1 and ℳ_2.



Algorithm <ref> gives the pseudo-code of the bisimulation based policy transfer algorithm of Castro et al. <cit.>. As only optimal actions of the source domain are the ones that get transferred, Castro et al. <cit.> define a simplified notation for the lax bisimulation distance as follows:


    d_≈(s_1, (s_2, a_2)) = d_L((s_1, π_1^*(s_1)), (s_2, a_2))


In step 6, LB(s_1, s_2) refers to the lower bound on the optimal Q-value of lax-bisimulation transferred actions defined in Corollary 11 of Castro et al. <cit.>. In step 8, the matching state in the source environment, s_match, is assigned such that it maximizes this lower bound. As Castro et al. note in <cit.>, this is a superior choice compared to the state that minimizes bisimulation distance alone. The transferred action, a_2^T, is the one that minimizes the bisimulation distance from the matching source state, s_match, and its optimal action, π_1^*(s_match).



Depending upon how d_≈(s_1, (s_2, a_2)) and d_≈'(s_1, s_2) are related, Castro et al. <cit.> define two variants of the lax bisimulation metric – optimistic and pessimistic.

    d_≈'(s_1, s_2) = max_a_2∈ A_2 d_≈(s_1, (s_2, a_2))   if pessimistic
    min_a_2∈ A_2 d_≈(s_1, (s_2, a_2))   if optimistic






























§ TRANSFER GUIDED EXPLORATION




In this section we present Transfer-guided Exploration (ExTra) as a novel directed exploration method for reinforcement learning that is based on the bisimulation transfer framework of Castro et al. <cit.>. The motivation is to use transferred knowledge from the optimal policy in a source domain to accelerate RL in a target domain – especially during the initial stage, when the domain-specific statistics used by traditional directed exploration methods are yet to be consistently estimated. We first present some results which relate bisimulation distance to the optimal advantage of an action in a target state.



 ∀ s_1∈ S_1, ∀ s_2∈ S_2, ∀ a_2∈ A_2, |V_1^*(s_1) - Q_2^*(s_2, a_2)| ≤ d_≈(s_1, (s_2, a_2)).



    |V_1^*(s_1) - Q_2^*(s_2, a_2)|    = |Q_1^*(s_1, π_1^*(s_1)) - Q_2^*(s_2, a_2)|
       ≤ |R_1(s_1, π_1^*(s_1)) - R_2(s_2, a_2)| 
          + γ T_K(d_≈)(P_1(s_1, π_1^*(s_1)), P_2(s_2, a_2))
       by similar argument as for Lemma 4 in <cit.>
       = d_≈(s_1, (s_2, a_2))




 ∀ s_1∈ S_1, ∀ s_2∈ S_2, |V_1^*(s_1) - V_2^*(s_2)| ≤ d_≈(s_1, (s_2, π_2^*(s_2))).


The goal of reinforcement learning is to get the agent to take optimal actions and the goal of efficient exploration is to achieve that fast. Hence, efficient exploration algorithms should be able to weigh the actions available in a given state on the basis of their potential optimality. In an MDP, ℳ = ⟨ S, A, P, R ⟩, the advantage of an action a∈ A in a state s∈ S with respect to a policy π is defined as A^π(s,a) = Q^π(s,a)-V^π(s). It quantifies the relative superiority of action a compared to the expectation under the policy over next actions. The optimal policy maximizes the optimal Q function: π^*(s)=argmax_a Q^*(s,a). Substituting the expression of Q in terms of advantage, we have: π^*(s) = argmax_a A^*(s,a)+V^*(s) = argmax_a A^*(s,a). Hence the optimal policy also maximizes the optimal advantage function. Given a source MDP, we derive a lower bound on the optimal advantage of available actions in a target state in terms of the lax-bisimulation distance function and use it as a measure of potential optimality.

 

Given MDPs, ℳ_1 = ⟨ S_1, A_1, P_1, R_1 ⟩ and ℳ_2 = ⟨ S_2, A_2, P_2, R_2 ⟩ and bisimulation metric d_≈:S_1× S_2× A_2→ℝ we have ∀ s_2∈ S_2, ∀ a_2∈ A_2

    A_2^*(s_2, a_2) ≥ -d_≈(s_match, (s_2, a_2))-β(s_2)

Where A_2^*(s_2, a_2) is the optimum advantage function in ℳ_2, s_match = argmax_s_1∈ S_1 V_1^*(s_1) - d_≈'(s_1, s_2) and β(s_2)=d_≈(s_match, (s_2,π_2^*(s_2))).



Since, V_2^*(s_2) = arg max_a_2∈ A_2 Q_2^*(s_2, a_2),  V_2^*(s_2) - Q_2^*(s_2, a_2) ≥ 0, and we have:

    V_2^*(s_2) - Q_2^*(s_2, a_2)    = |V_2^*(s_2) - Q_2^*(s_2, a_2)| 
       =  |(V_2^*(s_2) - V_1^*(s_match)) +
            (V_1^*(s_match) - Q_2^*(s_2, a_2))|
       ≤ |V_2^*(s_2) - V_1^*(s_match)| +
            |V_1^*(s_match) - Q_2^*(s_2, a_2)|
       ≤ d_≈(s_match, (s_2,π_2^*(s_2))) + d_≈(s_match, (s_2, a_2))
       (from Lemma <ref> and Corollary <ref>)
       = β(s_2) + d_≈(s_match, (s_2, a_2))

∴   A_2^*(s_2, a_2) = Q_2^*(s_2, a_2) - V_2^*(s_2) ≥ -d_≈(s_match, (s_2, a_2)) - β(s_2)
















Theorem <ref> gives a lower bound on the optimal advantage of an action in a target state in terms of the bisimulation distance to a source MDP. As explained in Section <ref>, Castro et al. <cit.> assign matching source state s_match to target state-action pair (s_2, a_2) following a minimum performance criterion in the form of a lower bound on Q_2^*(s_2, a_2). We choose to use s_match in Theorem <ref> to make sure that this minimum performance criterion is satisfied. While other bounds are possible for choices of s_1 ∈ S_1, s_1 ≠ s_match, they might not be usable, since they do not guarantee the performance bounds identified by Castro et al. <cit.>.







The bisimulation transfer algorithm of <cit.> maximizes a lower bound on the optimum advantage function A_2^*(s_2, a_2) of the target environment.



In bisimulation transfer, the transferred action a_2^T for target state s_2 is given by:

    a_2^T    = argmin_a_2∈ A_2 d_≈(s_match, (s_2, a_2)) 
       = argmax_a_2∈ A_2 -d_≈(s_match, (s_2, a_2))-β(s_2)

Since, β(s_2) is independent of a_2.

Note that Theorem <ref> and Corollaries <ref> and <ref> hold for both optimistic and pessimistic definitions of the lax bisimulation metric <cit.>.



Bisimulation Advantage: Given MDPs, ℳ_1 = ⟨ S_1, A_1, P_1, R_1 ⟩ and ℳ_2 = ⟨ S_2, A_2, P_2, R_2 ⟩ and bisimulation metric d_≈:S_1× S_2× A_2→ℝ we define the bisimulation advantage of an action a_2∈ A_2 in a state s_2∈ S_2 as: 


    A_≈(s_2, a_2)=-d_≈(s_match, (s_2, a_2))-β(s_2)

















We look to define a probability distribution over target actions that assigns higher probability to actions having higher bisimulation advantages. As, in general, the solution to argmin_a_2 d_≈(s_match, (s_2, a_2)) is non-unique, under bisimulation, multiple actions in the target environment could potentially map to the optimal action in the source environment. Among all policies that pick at least one of the actions that map to the optimal action under the bisimulation, by the principle of maximum entropy <cit.> , we choose one that assigns equal probability to all those actions. 
Softmax distribution satisfies this property. Hence we define the behavioral policy in Transfer-guided Exploration (ExTra) as a Softmax distribution over bisimulation advantages.

    π_ExTra(a_2|s_2, ℳ_1, π_1^*) = e^A_≈(s_2, a_2)/∑_b∈ A_2 e^A_≈(s_2, b)








In transfer-guided exploration (ExTra), the agent samples actions from π_ExTra(· | s_2, ℳ_1, π_1^*). Since the optimal policy in the target MDP, π_2^*, is not known during learning, β(s_2) can not be known exactly. Since β(s_2) (≥ 0) is the same for all actions in a given state s_2, replacing β(s_2) with a real positive number preserves the order of probability values assigned to different actions by π_ExTra. If transfer is successful, π_ExTra would assign higher probabilities to the optimal actions and thus help the agent to quickly arrive at the optimal policy. However, in the event of an unsuccessful transfer, π_ExTra may be biased away from the optimal actions. 
This may cause the agent to remain stuck with the wrong actions for long periods of time. 
In order to help the agent recover from the effect of unsuccessful transfer, we set β = α n, where α∈ℝ^+ is a tunable hyperparameter and n is the current step number. As n grows, π_ExTra(· | s_2, ℳ_1, π_1^*) tends to a uniform distribution over actions, thus annealing the influence of transferred knowledge on exploration with time. This does not hurt the agent's learning in states where the transfer was successful because the agent happens to have explored the optimal actions early on in training in those states. Note that changing β does not affect the rate of exploration; instead, it merely changes the shape of the probability distribution from which the agent samples actions during exploration. Algorithm <ref> gives an example use case of ExTra as an alternative to random exploration in ϵ-greedy Q-learning. Please refer to the Appendix section for more ways of using ExTra in conjunction with other traditional exploration methods.
















































































































































































§ EXPERIMENTAL RESULTS















In this section we present an empirical analysis of the performance of ExTra. We aim to address the following questions:

    
  * How does ExTra compare against traditional exploration methods?
    
  * How sensitive is ExTra to the choice of source task?
    
  * Can ExTra enhance the performance of other exploration algorithms that only use local information?
    
  * How does ExTra compare against Bisimulation Transfer?


We use the optimistic definition of the bisimulation metric in all our experiments as Castro et al. <cit.> note that it gives superior transfer results than the pessimistic definition.




 §.§ Evaluation metrics

The goal of this paper is to improve the rate of convergence of RL with the help of external knowledge transferred from a different task. The rate of convergence of an RL algorithm can be judged from a plot of Mean Average Reward (MAR) obtained by the agent over steps of training. Mean Average Reward is defined as follows:


Mean Average Reward: The average reward of a trajectory τ obtained by following a policy π is the average of all the rewards received by the agent in the trajectory. Mean Average Reward (MAR) of π is the mean of average reward for multiple trajectories rolled out from the policy.

    MAR(π) = 1/N∑_i=1^N 1/T_i∑_t=1^T_i R(s_t^i, a_t^i)

Where T_i is the length of the i^th trajectory.


The Area under the MAR Curve (AuC-MAR) is an objective measure of rate of convergence when the highest MAR values achieved asymptotically by all the candidate algorithms are the same <cit.>. A higher AuC-MAR implies higher rate of convergence. We use AuC-MAR for comparing the rates of convergence of RL algorithms using ExTra with the baseline methods. For the convenience of comparison, we report AuC-MAR as a percentage of AuC for the optimal policy (whose MAR is represented as a straight horizontal line through the steps of training but not shown in the plots to avoid clutter).


For measuring the relative improvement of the rate of convergence achieved by ExTra, we use Transfer Ratio, denoted by TR, defined as follows:


    TR = AuC-MAR with ExTra - AuC-MAR without ExTra/AuC-MAR without ExTra














 §.§ Experimental Design, Results and Discussion

We use stochastic grid-world environments of different levels of complexity (Figures <ref> and <ref>) for analysing the viability of ExTra. All of these environments have the common task of avoiding obstacles and reaching a goal. After being initialised with uniform probability from any of the grid-cells, the agent gets a reward of +1 on reaching the goal, -1 for stepping into a fire-pit and 0 elsewhere. The agent has four primitive actions: up, down, left and right. When one of the actions is chosen, the agent moves in the desired direction with 0.9 probability, and with 0.1 probability it moves uniformly in one of the other three directions or stays in the same place. If the agent bumps into a wall, it does not move and remains in the same state.
 

We choose Q-learning with four traditional exploration algorithms viz. ϵ-greedy uniform random exploration, MBIE-EB <cit.>, Pursuit <cit.> and Softmax <cit.> as baselines for comparison (see supplementary material for details of these algorithms). For ExTra, we train the optimal policy for the source domain using 
value iteration and calculate the optimistic bisimulation distance d_≈(s_1, (s_2, a_2)), ∀ s_1∈ S_1, s_2∈ S_2, a_2∈ A_2, tuning c_R and c_T for maximum transfer accuracy. We use the PyEMD library by <cit.> to calculate earth mover distance for the estimation of T_K(d) <cit.>. Our code is available on GitHub[https://github.com/madan96/ExTra]. The results reported for each baseline are obtained after rigorous tuning of their respective hyperparameters for the target domain. We report all MAR and AuC-MAR numbers as their mean ± standard deviation calculated over 10 different experiments with different random seeds. We tabulate the hyperparameter values in the Appendix section. 
















  §.§.§ How does ExTra compare against traditional exploration methods?

In our first set of experiments, we show that given an optimal policy for a related task-environment, ExTra can obtain faster convergence than traditional exploration methods that only use local information. We choose the , , and  environments shown in Figure <ref> as benchmarks. We train Q-learning agents with ϵ-greedy, MBIE-EB, Pursuit and Softmax explorations in these environments as baselines. For ExTra, we choose  in Figure <ref> as the source environment. We train an ϵ-greedy Q-learning agent (ϵ=0.2) that uses ExTra instead of uniform random for exploration (Algorithm <ref>) on each of the three target environments. Figure <ref> shows the variation of MAR over steps of training for the baseline as well as our ExTra agents. Table <ref> shows AuC-MAR values. We observe that our ExTra agent consistently achieves faster convergence in all the three environments. This corroborates our claim that ExTra can achieve faster convergence and hence superior sample efficiency if we have access to the optimal policy in a related task-environment. 





  §.§.§ How sensitive is ExTra to the choice of source task?


In this experiment we study the sensitivity of ExTra to the selection of source task. In our first study we consider transfer between tasks that share the same state-action space and reward structure but differ in goal positions. We construct 6 tasks in the  environment in which the  i^th task has its goal at the center of the i^th room (see Figure <ref>).
 
We use tasks 1 through 5 as source and task 6 as target. 
In our second study, we compare transfer from source tasks that differ in state space (), action space (), reward structure (, , ), goal distribution () and transition dynamics (). ,  and  are variants of the  environment with just three allowed actions (left, right, down), no goal at all and an added probability of 0.1 to slide downwards, respectively. The rest of the environments are as depicted in Figure <ref>. The target task-environment is . We report AuC-MAR values obtained by ϵ-greedy Q-learning with ExTra (Algorithm <ref>) for each of these source tasks in Tables <ref> and <ref>. 


We make the following observations:

    
  * In our first study (Table <ref>), each of our ExTra agents fetch higher AuC-MAR values than any of the baseline methods thus demonstrating the efficacy of ExTra. Also there is a rough trend of the AuC-MAR values decreasing with increasing distance of goal in the source task. This demonstrates graceful degradation of performance.
    
  * In our second study, ExTra beats both ϵ-greedy and MBIE-EB for even the worst case choice of source task -  (compare Table <ref> with Row 1 of Table <ref>). This is possible because ExTra is able to leverage knowledge about the transition dynamics of the source MDP (that are identical to the target MDP) even when the reward structures and goal distributions are drastically different. It also reflects the robustness of ExTra to the choice of source task.
    
  * We note that in Table <ref> the reward structure of the source environment has a more profound effect on the performance of ExTra than transition dynamics or goal distribution. This observation serves as a guide for choosing source environments for bisimulation transfer.
    
  * Higher AuC-MAR for  than  suggests that source MDPs with the same action space as the target are more favourable for ExTra even if the state spaces are different.
































































  §.§.§ Can ExTra enhance the performance of other exploration algorithms that only use local information?


We formulate ϵ-greedy versions of each of our baseline algorithms (ϵ=0.5), where the agent samples actions from π_ExTra with probability ϵ (ϵ=0.5) and follows the main algorithm rest of the time. Please refer to the supplementary material for pseudo-codes of these algorithms. We choose  as our benchmark environment and  (Figure <ref>) as source environment for ExTra. Table <ref> and Figure <ref> present the results of these experiments. 
We see that ExTra can provide improved rate of convergence of the traditional methods and hence can indeed be used as a complementary exploration method. 







  §.§.§ How does ExTra compare against Bisimulation Transfer?

To address this question we choose  as source environment. As target, we choose  and a modified version of the  environment of OpenAI Gym <cit.> with 54 states. The modified  environment has 3 rows, 3 columns and 2 drop locations at the top-left and bottom-right corners. The action space of this environment remains same as the original version, where the agent can choose actions from , , , ,  and . We compare the rates of convergence of ϵ-greedy Q-learning with ExTra and the bisimulation transfer algorithm of Castro et al. <cit.> that initializes the Q-matrix with the Q-value of the transferred policy. Figure <ref> presents the results of the experiments. We see that when the source and target tasks are similar ( and ) and bisimulation policy transfer is successful, Q-learning gets an initial jumpstart while ExTra catches up. When the source and target tasks are drastically different ( and ), the bisimulation distances are large and π_ExTra tends to a uniform distribution over target actions. As a result, ExTra falls back to vanilla ϵ-greedy Q-learning with uniform sampling. On the other hand, Q-learning initialized with bisimulation transfer has to first recover from the effect of negative transfer using ϵ-greedy uniform exploration before it can start learning. In this case, it does not get any jumpstart and also converges slower than ExTra which does not need to correct for the damage done by negative transfer and proceeds as vanilla ϵ-greedy Q-learning. We observe that, while bisimulation transfer can be both effective and fatal depending on how the source and target tasks are related, ExTra does not negatively affect the learning process even when the source and target task-environments are drastically different.
































































§ CONCLUSION


In this work we investigate the fundamental possibility of using transfer to guide exploration in RL and formulate a novel transfer guided exploration algorithm, ExTra, based on the theory of bisimulation based policy transfer in MDPs. We demonstrate that our method achieves faster convergence compared to traditional exploration methods that only use local information, is robust to source task selection and can complement traditional exploration methods by improving their rate of convergence. We also provide theoretical guarantees in the form of a lower bound on the optimal advantage of an action in the target domain in terms of bisimulation distance from the source environment. In our future work we plan to extend ExTra to larger state-action spaces and continuous control tasks, using differential and sampling-based methods for approximating the lax-bisimulation distance similar to <cit.>. An interesting direction of research could be to incorporate ExTra within the meta-RL framework for improving the meta-training and meta-testing sample efficiencies by leveraging knowledge from multiple source MDPs.


§ ACKNOWLEDGEMENTS

We gratefully acknowledge Pablo Samuel Castro of Google for helping us with the optimized implementation of bisimulation distance metrics and clarifying some crucial concepts regarding bisimulation based policy transfer in MDPs. Anirban Santara’s work in this project was supported by Google India under the Google India PhD Fellowship Award.


ACM-Reference-Format
  



§ APPENDIX

The full code-base is available open-source at <https://github.com/madan96/ExTra>



§ EXTRA VARIANTS OF TRADITIONAL EXPLORATION STRATEGIES













§ HYPERPARAMETERS FOR BASELINE EXPLORATION STRATEGIES







§ HYPERPARAMETERS FOR OPTIMISTIC BISIMULATION TRANSFER




