title: Multi-task Reinforcement Learning in Reproducing Kernel Hilbert Spaces via Cross-learning
authors: Juan Cervino Juan Andres Bazerque Miguel Calvo-Fullana Alejandro Ribeiro
text: 
  
  
  
  
  
  Multi-task Reinforcement Learning in Reproducing Kernel Hilbert Spaces via Cross-learning
  
      Juan Cerviño, Juan Andrés Bazerque, Miguel Calvo-Fullana, and Alejandro Ribeiro.
  
  This work is supported by ARL DCIST CRA W911NF-17-2-0181 and the Intel Science and Technology Center for Wireless Autonomous Systems.
  
  
  J. Cerviño, M. Calvo-Fullana, and A. Ribeiro are with the Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104, USA (e-mail: @seas.upenn.edu; @seas.upenn.edu; @seas.upenn.edu).
  
  
  J. A. Bazerque is with the Department of Electrical Engineering, School of Engineering, UdelaR, Uruguay (e-mail: @fing.edu.uy)  
  
  
  This work has been presented in part at the 2019 American Control Conference (ACC)<cit.>.
  
  
        ;  
  ===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  
  Reinforcement learning (RL) is a framework to optimize a control policy using rewards that are revealed by the system as a response to a control action. In its standard form, RL involves a single agent that uses its policy to accomplish a specific task. These methods require large amounts of reward samples to achieve good performance, and may not generalize well when the task is modified, even if the new task is related. In this paper we are interested in a collaborative scheme in which multiple agents with different tasks optimize their policies jointly. To this end, we introduce cross-learning, in which agents tackling related tasks have their policies constrained to be close to one another. Two properties make our new approach attractive: (i) it produces a multi-task central policy that can be used as a starting point to adapt quickly to one of the tasks trained for, in a situation when the agent does not know which task is currently facing, and (ii) as in meta-learning, it adapts to environments related but different to those seen during training. We focus on continuous policies belonging to reproducing kernel Hilbert spaces for which we bound the distance between the task-specific policies and the cross-learned policy. To solve the resulting optimization problem, we resort to a projected policy gradient algorithm and prove that it converges to a near-optimal solution with high probability. We evaluate our methodology with a navigation example in which agents can move through environments with obstacles of multiple shapes and avoid obstacles not trained for.
  
  
  
  Reinforcement learning, multi-task learning, meta-learning,  optimization.
  
  
  
  
  
  
  § INTRODUCTION
  
  
  
  Reinforcement Learning (RL) provides a framework for solving a wide variety of problems in which the system model is not available or it may be intractable <cit.>. The idea at the core of RL is that an agent can learn the optimal action to take from its experience, gained while interacting with the environment. Specifically, the agent is aware of its current state and chooses an action, after which the next state is reached. Subsequently, after each action is taken, the agent receives a reward from the environment, which regulates the value of the actions chosen. The agent's objective is to maximize the cumulative reward observed throughout the trajectory of states and actions. Being able to tackle complex systems, RL has found success in applications as diverse as autonomous driving<cit.>, robotics <cit.>, and smart grids<cit.>, among many others.
  
  Albeit showing success in tackling complex problems, in order to do so RL  requires a large number of samples collected from actions and state transitions. Besides, a policy that achieves good performance may work poorly at a different task, even if it is related or akin to the one trained for. The attempt to alleviate these issues is the goal of Multi-Task Learning (MTL) <cit.>, either seeking to leverage information in related tasks, or learning multiple tasks in a collective manner. In a general sense, these approaches exploit the fact that the data collected when learning one task can help learning other similar tasks. There are numerous ways of posing MTL problems. When studied for supervised learning, one could upper bound the distance between the weight vectors of different linear classifiers <cit.>. In the same vein, one could  use  convex local proximity constraints <cit.>. Other approaches attempt to regulate which task should be sampled by maintaining an estimate of each current performance<cit.>. Recently, a related approach named meta-learning <cit.>, has gained notorious popularity. The twist that makes it different from MTL is that the objective of meta-learning is to find a policy with good generalization with respect to unforeseen tasks. For the interested reader, a more exhaustive survey on multi-task learning can be found in <cit.>.
  
  In this work, we introduce a collaborative form of multi-task learning and meta-learning, which we denote as cross-learning. We introduce convex constraints in the policy space that bound the distance between task specific policies corresponding to different agents. Compared to previous approaches <cit.>, our work does not assume the relationships among tasks to be known. Furthermore, different from <cit.>, we avoid pair-wise constraints via the introduction of a central cross-learned policy. By nature of our proposed formulation, the benefits are twofold, (i) it produces a cross-learned policy that performs well for all the trained tasks, (ii) it produces an individual policy for each task that improves on an equivalent individual policy trained without cross-learning.
  
  We focus on policies which lie on a reproducing kernel Hilbert space, allowing for the approximation of a large class of functions <cit.>, and pose cross-learning  as a constrained RL problem. Then we show that the projection onto the resulting set of constraints can be cast as a Quadratically Constrained Quadratic Program (QCQP) <cit.>, and propose a projected policy gradient solution. 
  
  As an alternative, we offer a simplified formulation in which the coupling is relaxed to be satisfied on average by the policies. The simplified projection admits a closed form solution, both reducing the numerical burden of solving a  QCQP  per iteration, and clarifying the effect of the projection over the policies.     
  
  We show the convergence of the projected gradient ascent method to a neighborhood of the optimal solution with high probability. Further, to handle the memory explosion due to the increasing dimension of the kernel representations, we use <cit.> and <cit.> to project the policies to a lower dimensional space without sacrificing convergence guarantees. Finally we evaluate the proposed cross-learning approach in a navigation problem with multiple obstacles. We show that our cross-learning method produces policies that adapt to different scenarios outperforming their task-specific counterparts, particularly when facing objects not seen during training.
  
  The rest of the paper is structured as follows: Section <ref> introduces  RL  and its multi-task formulation. A treatment on how to solve the RL problem by means of gradient ascent is covered in Section <ref>. The aspects related to the necessary projection step in the cross-learning algorithm are covered in Section <ref>, with Section <ref> dedicated to its relaxed counterpart. The resulting cross-learning algorithm is covered in Section <ref>, with practical issues regarding policy representation being discussed in Section <ref>. Following, Section <ref>  provides a detailed analysis of  convergence,  with Section <ref> covering the assumptions taken to derive the results. The method is evaluated by means of simulations in Section <ref>, where a navigation problem is considered with single (Section <ref>) and multiple (Section <ref>) obstacles. Finally, Section <ref> closes the paper with some remarks and conclusions.
  
  
  
  § PROBLEM FORMULATION
  
  
  
  Before introducing our cross-learning formulation, let  us present the Markov decision process that models a single-task scenario. Consider two compact sets ⊂^q and ⊂^p, representing the possible states of an agent and the actions it can take. The agent takes actions sequentially. At time t, the agent is in state s_t ∈ and it takes an action a_t ∈, transitioning to a state s_t+1∈. The aforementioned dynamics are governed by transition probabilities, unknown to the agent, which satisfy the following Markov property, p(s_t+1=s | {s_l, a_l}_l≤ t)=p(s_t+1=s | s_t, a_t). Furthermore, each time that the agent takes an action and transitions into the next state, it receives a reward defined by a function r : ×→. 
  
  In order to decide which actions to take, the agent has a function h:→, called a policy, which in this work we assume to belong to a  reproducing kernel Hilbert space (RKHS) . By definition,  is a complete, linear function space endowed with a unique reproducing kernel κ̅:×→. We further define κ(s,s') as a diagonal matrix-valued function of size p× p where κ(s,s')_ii=κ̅(s,s').  Explicitly, every function h ∈ can be written as a linear combination of M kernels (including M=∞), i.e.,
  
      h(·)=∑_m=1^Mκ(s_m,·) w_m
  
  where w_m∈ denote the weights and s_m ∈ are called the kernel centers, or knots. Hence, every function h can be represented by a dictionary D_h = { s_1,…,s_M } and a set of weights W_h={w_1,…,w_M}. 
  
  
  For p=1,   ={κ(s,s'): s∈} is defined as a space of functions spanned by κ(s,s') where κ:×→ consists of a symmetric positive definite kernel,  and equipped with the inner product defined by the reproducing property ⟨κ(s,·),h(·)⟩=h(s). This inner product induces the norm h=(⟨ h,h⟩)^1/2 to be used henceforth. For p>1, κ(s,s')∈^p× p is a diagonal matrix whose entries satisfy the definition for p=1, and the inner product between two vector valued functions h and g aggregates the p products of their entries. Adopting vector-valued RKHS will allow to define a controller with multiple  outputs. The nonparametric nature of RKHSs translates into a rich space of policies that operate in continuous spaces, so that we can avoid discretizing  variables, optimizing over the policies directly instead of working with possibly inaccurate parameterizations.
  
  
  Based on its current state, the agent uses its policy to decide its next action to take. While deterministic policies i.e., a_t=h(s_t) are possible, in this work, we focus on stochastic policies. Policies with a random component foster exploration while offering several desirable properties <cit.>. To this end, we introduce zero-mean multivariate Gaussian noise n_t, which renders actions to be  a_t=h(s_t)+n_t. Equivalently, we can define the conditional probability of the action given the policy and the state  π_h (a | s ) : ×→ [0,1] as
  
      π_h(a|s)=1/ ( 2 πΣ )  
      e^-1/2(a - h(s) )^T Σ^-1(a - h(s) )
  
  where Σ is the covariance matrix of the Gaussian distribution. At time t, this is equivalent to acting by drawing a sample a_t ∼𝒩(h(s_t),Σ). Ultimately, the objective of the agent is to find a policy h that maximizes the expected discounted returns, given by
  
      U(h) ≜_s,a[∑_t=0^∞γ^t r(s_t,a_t)| h],
    
   where γ∈ (0,1) is the discount rate. Lower discount rates γ favor myopic agents only concerned about the near future, while   γ closer to 1 corresponds to farsighted agents that value future rewards more prominently <cit.>. The expectation in (<ref>) is taken with respect to the whole trajectory of states and actions. 
   
  
  
   §.§ Multi-task Reinforcement Learning
  
  
  
  Now, we consider the case of multiple tasks. Specifically N tasks, each of them with its expected discounted return U_i, for i=1,…,N. The goal of our multitask RL methodology is to learn individual h_i for each task and a common policy g with acceptable level of performance for the tasks. It is expected that information from different tasks would enable enhanced learning performance if the reward data associated to these tasks is correlated. A simple approach would be to directly obtain the individual policies h_i that maximize the discounted return of each of the N tasks separately. Namely,
  
      PI{ h_i^⋆}= h_i∈ℋ  U_i (h_i).
  
  The problem with this formulation is that it is entirely distributed. Hence, this approach is unable to provide any form of generalization across tasks. In other words, and individual policy h_i^⋆ obtained by computing (<ref>) maximizes the expected discounted reward U_i but it is not trained to achieve any level of performance in U_j for j ≠ i, rendering no generalization performance across tasks. Furthermore, since, each policy h_i^⋆ is obtained separately by maximizing a particular expected return U_i, the data used for policy h_i^⋆ does not contribute to the learning of policies h_j^⋆.
  
  The other possible extreme  would be to force a single policy g to maximize the average expected discounted return U_i over the N tasks, therefore learning a policy that perform well on average for all tasks. That is, 
  
      g^⋆= g∈ℋ 1/N∑_i=1^N U_i (g).
      PII
  
  The intuition being this formulation is that while the expected discounted returns of each task U_i might be different from each other, there might exist some correlation among them. However, adopting a common policy g  reduces the adaptability of the learning algorithm to each specific tasks. Besides, when policy g^⋆ is analyzed separately, say for a particular task U_i, nothing guarantees individual task performance. 
  
  
  
   §.§ Cross-learning
  
  
  The drawbacks of the previous approaches are apparent. They either aim to obtain individual policies, as in (<ref>), or a central policy as in (<ref>). In order to leverage experience among tasks and achieve a generalization performance we introduce our cross-learning framework. This formulation aims to learn a family of individual task policies h̅_i together with a cross-learned policy g̅ by solving the following optimization problem,
  
  
      PCL{h̅_i},g̅=h_i,g∈     ∑_i=1^N  U_i (h_i)  
      subject to      h_i - g ≤ϵ,    i=1,…,N.
  
  
  The key guiding principle of our framework is the search for policies that stay close together in the optimization space via the introduction of a measure of centrality ϵ. This novel formulation allows each policy h_i to train in it specific expected discounted return U_i while forcing centrality through the cross learned policy g. Note that since the central policy g̅ is not forced to maximize the sum of expected discounted returns, g will be close to all optimal policies h̅_i but not necessarily perform on the average of the expected discounted returns as in (<ref>).
  
  For values of ϵ sufficiently large,  the constraint in (<ref>) becomes inactive, rendering problems  (<ref>) and (<ref>) equivalent. Problem (<ref>) can be seen as the unconstrained version of problem (<ref>). Likewise, setting ϵ=0 forces a consensus constraint in which all policies h_i are equal one another, yielding problems (<ref>) and (<ref>) equivalent. Otherwise the h_i policies are brought closer together at the cost of reducing each task's utility, in exchange of better generalization performance. 
  
  With the fully distributed formulation (<ref>) each agent achieves  a specific-task,  adjusting its policy  h_i separately to optimize its own  expected cumulative reward U_i as in (<ref>). In this way, different agents optimize for their own rewards, being agnostic of other agents and their tasks. In contrast, the cross-learning formulation (<ref>) couples the rewards through the centrality constraint, bringing policies together and causing the reward information of an agent to spread to the policies of all other agents. The bound ϵ is a bargaining parameter that tunes how much the goals of others affect each agent policy.
  
  So far we have assumed that the expectations that define each U_i are computable. Otherwise, agents can solve problems (<ref>) and (<ref>) via  stochastic RL algorithms as given in Section <ref> for the case when the rewards are not available in closed-form and policies are learned from data. Various learning algorithms exist, but they share in common that the policies are improved sequentially by incorporating reward data that the agents collect while they take actions. An agent running an RL algorithm for (<ref>) would learn from its own task-specific reward data. Instead, our cross learning formulation yields an RL algorithm in which data acquired  by all agents across tasks percolates through the centrality constraint. Collecting data from multiple sources enables  enhanced learning performance if these sources are correlated, specially at early stages of the learning process when the amount of data collected per task is limited. In addition, the common policy g can also be used as an after-training policy. This would be the case of an algorithm that, after being trained for multiple tasks, needs to quickly adapt to one of these tasks without necessarily knowing which one. In this sense, this is similar to finding a good initialization point of a learning algorithm for a family of tasks {U_i}.
  
  
  
  § STOCHASTIC POLICY GRADIENT
  
  
  
  Now that we have formulated the cross-learning problem we will attempt to solve it. Two immediate issues need to be addressed before proceeding to obtain the solution to problem (<ref>). First, we will resort to gradient ascent on the objective of the problem, the form of which is given by the policy gradient theorem <cit.>. Secondly, we need to address the constraints. While we could resort to primal-dual methods<cit.> to overcome this issue, we prefer to exploit the structure of the set of constraints which form a convex set. Hence, we can compute the projection to this set at each step of the gradient ascent. In this section, we will  focus on the computation of the gradient leaving the projection step for next section. Ignoring the constraints ||h_i-g|| ≤ϵ, the update step (pre-projection) for policy h_i at iteration k is given by
  
      h̃_i^k=h_i^k+η∇_h_i U_i (h_i^k) ,
   
  where η∈ (0,1) corresponds to the step size. Upon defining the Q-function Q_i:× A→
  
      Q_i(s,a;h_i) ≜[∑_t=0^∞γ^t r_i(s_i,t,a_i,t)| h_i, s_i,0=s, a_i,0=a],
  
  it  is shown in <cit.>,<cit.> that
  
      .∇_h_i U_i(h_i)|_s=s'= 
         1/1-γ𝔼_(s,a)∼ρ_i[ Q_i(s,a;h_i)κ(s,s')Σ^-1(a-h_i(s)) | h_i],
  
  where the expectation in (<ref>) is taken with respect to discounted occupation measure,
  
      ρ_i(s,a) ≜ (1-γ)∑_t=0^∞γ^t p(s_i,t=s,a_i,t=a).
  
  
  The probability density function in (<ref>) depends on the transition probabilities of the system as well as the agent's policy. This can be shown by expanding the joint probability, which leads to the following expression.
  
      ρ_i(s,a)=1/1-γ∑_t=0^∞γ^tπ_h_i(a_i,t|s_i,t) 
               ×∏_u=0^t-1 p(s_i,u+1|s_i,u,a_i,u)π_h_i(a_i,u|s_i,u) p(s_i,0).
   
  Since the agent is assumed to not have access to the state transition probabilities, the only available resources to the agent are the states, actions and rewards over a trajectory. This means that the expectation in U_i (h_i) as well as its gradient ∇_h_i U_i(h_i) are not computable. However, we can construct an unbiased estimate ∇̂_h_i U_i using the available states s_i,t, actions a_i,t and rewards r_i,t. Two challenges arise in the search for such an estimate. First,  we need to estimate the Q-function Q_i(s,a), and secondly, we need to sample from the distribution ρ_i(s,a). 
  
  An unbiased estimate Q̂_i(s,a, T) can be found by sampling a geometric variable T with parameter γ, such that P(T=0)=1-γ, and adding T consecutive rewards <cit.>,<cit.>  
  
      Q̂_i(s,a, T)=∑_τ=0^T r_i,τ.
  
  These rewards are collected by an agent following a trajectory of T steps, starting from state s and action a, and using policy h(s) for selecting actions henceforth. 
  
  
  
  Next we use (<ref>) to find an unbiased estimate of the gradient sampling from (<ref>), i.e., 
  
      .∇̂_h_i U_i(h_i)|_s=s'=1/1-γQ̂_i(s,a,T)κ(s,s')Σ^-1(a-h_i(s)).
  
  For (<ref>) to be unbiased, the pair (s,a) must be sampled from the distribution in (<ref>). The procedure to find such a pair  is shown in Steps 1-4 of Algorithm <ref>. Starting from  (s_i,0,a_i,0) and selecting the actions according to h_i(s), the agent runs t steps of a trajectory  with t drawn  from the same  geometric distribution again. The final pair  (s,a)=(s_i,t,a_i,t) follows the desired distribution ρ(s,a)  <cit.>.
  
  The remaining steps of Algorithm <ref> are simply an ordered list of instructions to obtain   ∇̂_h_i U_i in (<ref>).
  Intuitively, selecting a geometric random variable yields a future time instant such that s_i,t is representative of the whole trajectory.  The weight ŵ_i,t represents a stochastic sample of the gradient around s_i,t.  The estimate includes a kernel function κ(s_i,t,s') which interpolates the gradient to nearby states s'.
  This results in the unbiased estimate of ∇̂_h_i U_i as stated in the following proposition, which is brought  from <cit.>.
  
  The stochastic gradient ∇̂_h_i U_i is unbiased; i.e.,  [∇̂_h_i U_i]=∇_h_i U_i.
  
  
  The proof can be found in <cit.> for a generalized version of Algorithm <ref> with two-sided weights.
  
  Using this result we run a stochastic gradient ascent iteration, given by the following expression
  
      h̅_i^k=h_i^k+η^k ∇̂_h_i U_i (h_i^k).
   
  For each step, a new element η^k ∇̂_h_i U_i is added to policy h_i in order to obtain policy h̅^k_i. More specifically, the dictionary and weights  of policy h̅_i have new  elements, s_i,t and w_i,t=ηŵ_i,t, respectively. State s_i,t stands as a  knot that specifies a new kernel which is combined into the policy. This procedure presents a major drawback due to memory explosion, with infinite kernels expanding the policy.  This problem is addressed by the pruning procedure discussed in the Appendix <ref>. The procedure is based on <cit.> and discards kernels that are not informative.
  
  While  (<ref>)  is provably unbiased    and  (<ref>)  has theoretical convergence guarantees <cit.>, the variance of  (<ref>)  may be high reflecting on a slow  speed of convergence of (<ref>).  For these reasons, the literature on RL includes several practical improvements. Variance can be reduced by including batch versions of the  gradient method, in which several stochastic gradients are averaged before performing the update in (<ref>). One particular case of a batch gradient iteration in   <cit.>, averages two gradients sharing the same state s_i,t but with actions a_it and a'_it  in opposite directions. This results in a  gradient that favors the action with higher Q̂(s_i,t,a). Similarly, using estimates of the advantage function A(s,a)=Q(s,a)-V(s) with respect to the value function V(s)=E_a[Q(s,a)]  the gradient favors actions such that Q(s,a) outperforms its average <cit.>.     
  Besides these variants for estimating ∇_h_i U_i, there are several flavors of the stochastic algorithm (<ref>) that combine subsequent gradients in the update for the purpose of introducing inertia. A prominent example of such an algorithm is the  ADAM optimizer  <cit.>.
  
  With  any of these RL variants being selected, we proceed to combine the stochastic gradients across tasks for a cross-learning algorithm that solve the problem (<ref>).
  
  
  
  
  
  
  
  
  
  § PROJECTED POLICY GRADIENT
  
  
  
  In the previous section, we studied the required steps to compute the gradient update  for  the cost of the cross-learning problem (<ref>). Subsequently, the policy that results from the gradient update needs to be projected to the  constraint set in (<ref>). To this aim, we dedicate the section to this projection.
  
  Let  {h̅_i,g̅} denote the set of policies that result from the gradient step  in (<ref>). Notice that since the  cross-learned policy g is not a variable in the cost, it  remains unchanged after the gradient step. Let _[h̅_1,…,h̅_N,g̅] denote the projection of h̅_1,…,h̅_N,g̅ into the set of constraints ={h_i,g∈: h_i-g≤ϵ}, which is defined by
  
  
  
      _[{h̅_i},g̅] =   {h_i},g  ∑_i=1^N h_i - h̅_i ^2 + g - g̅^2   
         subject to   h_i - g ^2 ≤ϵ^2,    i=1,…,N.
  
  
  
  Given _, the projected stochastic gradient ascent update for problem (<ref>) with step size η^k takes the form
  
  
      ({h_i^k+1},g^k+1)=_[{ h^k_i+η^k ∇̂_h_i U_i(h_i^k)}, g^k],
  
  
  which takes into account that the gradient of  U_i with respect to g is null. The following lemma, which will be called upon throughout the section, establishes that the solution h_i  lays inline between  h̅_i and g, and establishes a useful equation.  
  
  If (g̅,h̅_1,…,h̅_N) and ( g, h_1,…, h_N) are the input and output of the projection operator  _ then 
  
      h_i   = ζ_i h̅_i +(1-ζ_i)  g
  
  with ζ_i ∈ [0,1]⊂,
  and 
  
      g-g̅   =  ∑_i=1^N (h̅_i -h_i).
  
  
  
  Writing the Lagrangian for (<ref>) with scalar multipliers μ_i≥ 0, i=1,…,N and setting its derivatives with respect to g and h_i to zero, it yields
  
      h_i-h̅_i+μ_i (h_i-g)   =0
      
      g-g̅+∑_i=1^N μ_i(g-h_i)   =0 .
  
  Equation (<ref>) can be rearranged into h_i=1/1+μ_ih̅_i +μ_i/1+μ_i g, which coincides with (<ref>) for ζ_i=1/(1+μ_i). Also, adding (<ref>) over i and substituting the sum in (<ref>) results in (<ref>).
        
  
  
  
  Fig. <ref> shows the effect of  the projection _ in a simplified case. For the illustration  purpose of Fig. <ref>, replace the RKHS  by the standard vector space  ^2. In this case we solve (<ref>) and obtain that  vectors h_i lay at the intersection of the line connecting  h̅_i with  g (cf., (<ref>)), and the circumference of center g and radius ϵ. Policies h_i are brought together close to the common center g, half-way between the fully separable version (<ref>) in which h_i=h̅_i, and the strict solution (<ref>) in which all the h_i would be forced to be equal.
  
  Returning to the  RKHS case in which  g, h_i∈, the following proposition demonstrates  how to project h̅_i and g̅ into  by solving a standard  Quadratically Constrained Quadratic Program (QCQP). We focus on the case p=1 since a generalization is simple but the notation more involved. The following  assumption, which   will be satisfied by the RL algorithm, states that the h̅_i are finite dimensional, they share L kernels s_1,…,s_L with g̅, and differ  in a unique kernel s_L+i.
  
  
  
  Functions g̅ and h̅_i are given by finite sums of weighted kernels with the following structure h̅_i=∑_m=1^L+Na̅_miκ(s_m,s),  where  a̅_mi=0 for m>L, m≠ L+i and  g̅=∑_m=1^L+Nc̅_mκ(s_m,s) where c̅_m=0 for m>L.
  
  
   For notation brevity, collect the coefficients  a̅_mi and c̅_m in  a matrix A̅∈^(L+N)× N and a vector c̅∈^(L+N), respectively. Also define  1_N∈^N as the vector of all ones, and  K∈^(L+N)×(L+N) as the kernel Gram matrix with elements κ(s_m,s_m'). Under this definitions the projection can be solved as a QCQP, as detailed in the following proposition.
  
  
  If  h̅_1,…,h̅_N, g̅∈ satisfy Assumption <ref>, then  the solution to (<ref>)   is given by 
  	
      h_i   =∑_m=1^L+N  a_miκ(s_m,s),   
       g=∑_m=1^L+N  c_mκ(s_m,s),
  
  where the coefficients a_mi, c_m, are the entries of the matrix A∈^(L+N)× N and vector c∈^(L+N)  that solve the following problem
  
  
      c
        		A ∈^(L+N)× N
      
        		c∈^L+N
           ((A̅-A)^T K (A̅-A))+(c̅-c)^T K (c̅-c)  
           ((A-c1_N^T)^TK(A-c1_N^T))≤ϵ^2 1_N .
  
  
  
  
  
  
  It follows from Lemma <ref> that h_i and g are linear combinations of  h̅_i and g̅, and thus they   admit the finite dimensional expansions in (<ref>). 
  The QCQP in (<ref>) follows from expanding the norms in (<ref>) according to (<ref>).
  
  
  
  
   §.§ Relaxed Projection
  
  
  
  As per Proposition <ref>, in order to solve the cross-learning problem (<ref>), we need to solve a QCQP at each gradient step, which may become computationally expensive for policies represented with a large amount of kernels. For a simplified closed-form solution to the projection (<ref>), we consider the following relaxation of the cross-learning problem (<ref>) which we denote as relaxed cross-learning,
   	
  	
  
      RCLh_i,g∈maximize     ∑_i=1^N  U_i (h_i)  
      subject to     ∑_i=1^N  h_i - g ^2 ≤ N ϵ^2.
  
  
  
  The main difference between the original cross-learning problem (<ref>) and its relaxed counterpart (<ref>) is the number of constraints. In the relaxed cross-learning problem (<ref>) there is only one constraint, which is specified as the average over the N constraints of the original problem. This results in the reduction to a single Lagrange multipliers, which renders a closed-form solution that can be computed exactly without the need of solving an optimization problem numerically. The associated projection of the relaxed cross-learning problem is,
  
  
  
      _[{h̅_i},g̅] =   h_i,g  ∑_i=1^N h_i - h̅_i ^2  
         subject to  ∑_i=1^N  h_i - g ^2 ≤ N ϵ^2.
  
  
  
  
  Notice that we have omitted the term g - g̅^2 in the cost of (<ref>). This simplification plays an important role in obtaining a simpler closed form solution. Notice also that the set of constraints ={h_i,g,∈: ∑_i=1^N  h_i - g ^2 ≤ N ϵ^2} contains the previous set , namely,  is a relaxation of . 
  
  
   
  In Fig. <ref> we can see the solution of relaxed projection _ given by equations (<ref>) superimposed to the solution of the original projection _ given by equations (<ref>). Notice that the centers g resulting from both projections are shifted one from another, and that the points h_i in the relaxed version are not at distance ϵ from the center policy, as it results when using the original projection _.  
  
  Now, after qualitatively comparing the original projection _ to its relaxed version _ , we will delve into the closed-form solution of the latter. As given in (<ref>), _ admits the following  closed-form solution. 
  
  
  Given  h̅_1,…,h̅_N ∈,  the solution of (<ref>) takes the form
  
      g   =1/N∑_i=1^Nh̅_i,     h_i=(1-ψ) g +ψh̅_i,
  
  where ψ=min{1,Nϵ(∑_i,j=1^Nh̅_i-h̅_j^2 )^-1/2}.
  
  
  
  
  Equations (<ref>) follow from setting to zero the derivatives of the Lagrangian for (<ref>) with multiplier μ=1/(1-ψ). Then  ψ=1 holds when the constraint of (<ref>) is inactive, and  ψ=Nϵ(∑_i,j=1^Nh̅_i-h̅_j^2 )^-1/2    is obtained   by imposing the constraint to be active and substituting h̅_i -g^2 = 1/N∑_j=1^N(h̅_i-h̅_j)^2.
  
  
  As in the case of the original projection _ (cf. Lemma <ref>), the solutions h_i of the relaxed cross-learning projection _ lie on the inline between h̅_i and g. 
  
  
  From Propositions  <ref> and <ref> it follows that the output of the projections, both the original one and its relaxed version,  renders policies that share the same kernels. This observation is  instrumental for algorithmic reasons, as it allows us to keep a common dictionary of kernels for all policies. Nevertheless, the size of such dictionary grows linear with the number of iterations. This problem must be handled adequately as otherwise it would lead to memory explosion. The details of this problem and the proposed solution are discussion on the following Section <ref>.
  
  
  We finish this section by comparing the solutions of the original and relaxed projections, _ given by (<ref>) and _ given by (<ref>), to corroborate the observations in Fig. <ref>. Specifically, we prove that if the input center policy g̅ is close to the mean of the input policies, then the two projected centers are close one each other and the difference between the individual policies is bounded.
  
  
  	Let (g,h_1,…,h_N) and (g',h'_1,…,h'_N) be the solutions to problems (<ref>) and (<ref>), respectively. Then, if g̅-g'≤ϵ, it follows that g-g'≤ϵ. Moreover, the individual policies satisfy 
  	
      h_i-h'_i   ≤ϵ( 2 + √(N y_i/∑_i y_i))
  
  	where y_i^2=h̅_i -g'^2 = 1/N∑_j=1^N(h̅_i-h̅_j)^2.   
  
  
  According to Lemma <ref> g, h_i and h̅_i are aligned, hence we can write  
  
      g   =h_i+δ_i v_i
  
  where v_i=(g-h̅_i)/g-h̅_i has norm one and  δ_i≤ϵ, with equality if the constraint is active.
  Define u=g̅-g' such that  u≤ϵ by assumption.  
  Combining (<ref>) with (<ref>), together with g'= 1/N∑_i=1h̅_i and   g̅-g'=u, it follows
  
      g-g'   =g-g̅ + g̅ -g'=∑h̅_i -∑ h_i +u
         = N g' -   ∑_i  (g -δ_i v_i) +u .
  
  After rearranging terms, the triangle inequality yields
   g-g'≤1/N+1(u + ∑_i δ_i v_i) ≤ϵ,  as desired. 
  
  Using the bound g-g'≤ϵ  just found, we proceed to bound the difference between the individual policies.   
  Adding and subtracting g and g' and then applying the triangle inequality we obtain
  
      h_i-h'_i   ≤h_i-g + g-g' +g'-h'_i.
  
  The first term  satisfies h_i-g≤ϵ because h_i and g are feasible. The second term is also lower than ϵ, since g-g'≤ϵ, as previously found. To conclude the proof, observe that according to (<ref>)  g'-h'_i^2=ψ^2 y_i^2≤ Nϵ^2 y_i^2/∑_i y_i^2. 
  
  
  
  
  
  § CROSS-LEARNING ALGORITHM FOR REINFORCEMENT LEARNING
  
  
  
  By the combination of both the gradient step presented in Section <ref> and the projection discussed in Section <ref>, we obtain the cross-learning algorithm. The resulting strategy proposed in this paper involves combining the information collected by all agents and projecting them into the set of constraints . Furthermore, we substitute the gradient  ∇_h_i U_i  in (<ref>) for a stochastic estimate ∇̂_h_i U_i obtained by following Algorithm <ref>, which results in a stochastic version of the projected gradient ascent method; i.e., 
  
  
      ({h_i^k+1},g^k+1)   =_[{ h^k_i+η^k ∇̂_h_i U_i(h_i^k) }, g^k].
  
  
  The overall resulting method is summarized in Algorithm <ref>. The cross-learning procedure first collects all the stochastic gradients of the expected reward for each task following the task specific policy ∇̂_h_iU_i.  Then, the policies are brought together to the distance constraints by the projection _. The projection _[·] into set  can be replaced by its relaxed counterpart  _[·] if computation resources are limited. Afterwards, Algorithm <ref> has a step to reduce dictionary complexity, named Common Dictionary Kernel Orthogonal Matching Pursuit (CDKOMP), which we discuss next in Section <ref>. The algorithm has a stopping condition given by ⟨∇̂_h_iU_i (h_i^k+1), (h-h_i^k+1) ⟩≤α.
  
  
  
  
  
   §.§ Reducing the Dictionary Complexity
  
  
  
  The cross-learning algorithm suffers from a practical drawback that need to be addressed. New kernels are added per policy during each step of the gradient ascent algorithm, leading to memory explosion.  This issue arises due to the stochastic gradient produced by Algorithm <ref>, which results in the addition of a new kernel κ(s_i,t,·) to the dictionary of policy π_i per gradient step. Therefore, there are N new kernels per itaration, one per policy. Furthermore, by performing linear combinations of all policies, the projection (<ref>) (or its relaxed counterpart (<ref>)) add all these  new knots to the dictionary of each single policy.
  
  To overcome this limitation, we reduce the dictionary elements via Common Dictionary Kernel Orthogonal Matching Pursuit (CDKOMP). This procedure performs an additional projection to a lower dimension at each gradient step which both keeps the memory bounded and merges the policies dictionaries. The less informative kernels  in the dictionaries are discarded, keeping only  those that expand the current policies h_i^k and g^k up to a prescribed level of precision β. The algorithm, which is based on Kernel Orthogonal Matching Pursuit <cit.>, induces bias that is bounded at all times. Specifically, the CDKOMP introduces bias terms b_i^k to policies h_i^k+1 and b^k_N+1 to policy g^k+1 all bounded at all steps, i.e., 
  
      ({h_i^k+1},g^k+1)   =_[{ h^k_i+η^k ∇̂_h_i U_i(h_i^k) }, g^k] 
      
         + ({b^k_i},b_N+1^k),
  
  with ||
  b^k_i||<β, k=1,…,K, i=1,…,N+1. An in-depth explanation of the procedure can be found in Appendix <ref>.
  
  
  
  
  § CONVERGENCE OF THE CROSS-LEARNING ALGORITHM
  
  
  
  In this section we provide  convergence guarantees of the cross-learning Algorithm <ref> to a near-optimal point with high probability. 
  
  
  
   §.§ Properties and Assumptions
  
  
  
  As a base for convergence analysis, we introduce a set of assumptions that need to be satisfied for all tasks.
  
  
  The norm of the gradient of the expected discounted returns ∇_h_i U_i is upper bounded by a constant μ_i, i.e., for any policy f
  
      ||∇_h_i U_i (f)|| ≤μ_i.
  	
  
  
  
  The gradients of the expected discounted return ∇ _h_i U_i are Lipschitz continuous with constant L_i, i.e., for any two  policies f_1,f_2, 
  
      ||∇_h_i U_i (f_1)-∇_h_i U_i (f_2)||≤ L_i ||f_1-f_2||.
  
  
  
  
  The expected norm of the square of the stochastic gradient of the expected discounted return U_i is upper bounded, i.e., for any policy f
  
      [||∇̂_h_i U_i (f)||^2]≤ B^2_U_i.
  
  
  
  
   
  	Given a batch size number b_U_i used to obtain the stochastic gradient of the expected discounted return ∇_h_i U_i, its second moment is upper bounded, i.e., for any policy f
  	
      [||∇̂_h_iU_i(f) - ∇_h_i U_i(f)||^2] ≤σ_U_i^2/b_U_i.
  
  
  
  Notice that all of these statements are standard assumptions when dealing with constrained non-convex stochastic optimization problems. Furthermore, they can be shown to be satisfied by  assuming that the reward functions r_i(s, a) are upper bounded <cit.> . 
  
  Under these assumptions the proposed method takes the form of a nonconvex projected stochastic gradient ascent algorithm. Therefore, the following convergence analysis for cross-learning makes use of the usual approach to the analysis of these kinds of algorithms. Specifically, we follow an approach similar to that of <cit.>, with the resulting statements tailored to our framework, including the bias introduced by the CDKOMP Algorithm <ref>, the multi-task formulation and the lack of gradient update for the cross-learning policy g.
  
  
  
   §.§ Convergence Analysis
    
  
  For convenience, we begin by defining the cross-learning function F : ^N →, which corresponds to the objective function of the cross-learning problem (<ref>). This function receives a vector of policies h=[h_1,…,h_N] and returns the sum of the expected discounted returns of each policy U_i(h_i). Namely,
  
      F(h)=∑_i=1^N U_i(h_i).
  
  Further, we define the gradient of the the cross-learning function F with respect to the policy vector h is given by a vector of the gradients of each expected discounted return U_i with respect to each policy h_i, i.e.,
  
      ∇_h F=[∇_h_1U_1,…,∇_h_NU_N].
  
  Now, let us recall the standard criterion for local maxima (also denoted as a first-order stationary point) over a convex set of constraints .
  
  If h_i^⋆ is a local maximum of the function U_i over the convex set of constraints , then
  
      ⟨∇_h_i U_i (h_i^⋆), (h-h_i^⋆)⟩≤ 0,   ∀ h ∈.
  	
  
  
  See e.g., <cit.>.
  
  Notice that, under this condition, if the local maximum of the function U_i is attained by a policy h_i^⋆ inside of the convex set of constraints , then the gradient must be zero, i.e. ∇_h_i U_i (h_i^⋆)=0. In the case that  h_i^⋆ is not in the interior of the set of constraints , then ⟨∇_h_i  U (h_i^⋆), (h_i-h_i^⋆)⟩ < 0. 
  
  Ideally, the objective would be for Algorithm <ref> to achieve a local maximum, for the sum of expected discounted returns of all policies, namely, the cross-learning function defined in equation (<ref>). However, there are practical issues that need to be taken into account. First, it may not be possible to converge to h_i^⋆ in a finite number of steps, rendering problem (<ref>) unsolved. On the other hand, if an accuracy level α is admissible, then a neighborhood of the solution h_i^⋆ may be reached in a moderate number of iterations, and the cross-learning Algorithm <ref> can be stopped. Thus, we introduce the following definition.  
  
  Given α>0,  h_i^K is a α-First-Order Stationary Point (α-FOSP) of the function U_i over the convex set  if
  
      ⟨∇_h_i U_i (h_i^K), (h-h_i^K) ⟩≤α,   ∀ h ∈.
  
  
  
  Notice that Definition <ref> is an α-relaxation of the standard criterium of a local maximum, rendering equal solutions h_i^K=h_i^⋆ if α=0 (cf. Proposition (<ref>)). Still, the α-FOSP condition is not readily met by the stopping condition of the cross-learning algorithm. Since we are unable to compute the value of the expected discounted returns U_i, nor obtain its gradient ∇_h_i U_i,  Algorithm <ref> utilizes an unbiased estimate of the gradient of U_i, namely ∇̂_h_i U_i, as the stopping condition. Hence, given α >0, the cross-learning algorithm will stop at iteration k=K if for all tasks, the following condition is met,  
  
      ⟨∇̂_h_i U_i (h_i^K), (h-h_i^K)⟩≤α,   ∀ h ∈.
  
  Notice that equation (<ref>) is the stochastic version of equation (<ref>), meaning that for condition (<ref>), the stochastic gradient of ∇_h_i U_i, given by ∇̂_h_i U_i is used instead. Another way of expressing the stopping condition of is by its maximum inner product. Hence, the stopping condition of the cross-learning algorithm can be equivalently given by,
  
      max_h ∈i ∈{1,…,N}⟨∇̂_h_i U_i (h_i^K), (h-h_i^K)⟩≤α.
   
  Notice that imposing the condition (<ref>) for all tasks i=1,…,N is not the same as using the cross-learning function ⟨∇̂_h F(h^K),(h-h^K)⟩≤α, since we need to ensure that the condition is satisfied for each task. 
  
  Now, the challenge arises when using the stochastic condition (<ref>) to stop the cross-learning algorithm, because the α-FOSP condition (<ref>) is defined for  the  deterministic gradient. In the following, we show that if condition (<ref>) is met for a given α>0 and a set of i =1,…,N tasks by a sequence of K iterates generated by Algorithm <ref>, then with high probability the resulting policy h^K is an α-FOSP of problem (<ref>). 
  
  We start by showing that before the stopping condition is met, the expected difference between the cross-learning function F at two subsequent iterations h^k and h^k+1, with k<K, is lower bounded.
  
  
  Consider the iterates 𝐡^k generated by Algorithm <ref> and the cross-learning function F defined in (<ref>). If Assumptions <ref>-<ref> hold then, for all iterations before the stopping time condition (<ref>) is met, i.e. with k<K,  the expected difference in the function F between two subsequent iterations, h^k and h^k+1 is lower bounded by
  
      [F(h^k+1)-F(h^k)]≥γ_F,    k<K,
  
  where the constant γ_F is given by 
  
      γ_F=α-3(N+1)β^2L_max- √(N+1)β∑_i=1^Nσ_U_i/√(b_U_i)
         - √(N+1)β∑_i=1^N μ_i - (3 η^2 L_max+η)(∑_i=1^N B_U_i^2)
         -η∑_i=1^N μ_i(∑_i=1^N σ_U_i/√(b_U_i))-η(∑_i=1^N σ_U_i/√(b_U_i))^2
         -√(N+1)β(∑_i=1^N σ_U_i/√(b_U_i)),
  
  where η≜sup_k η_k and L_max≜max_i L_i.
  
  
  See Appendix <ref>. 
  
  
  The previous lemma shows that by using the iterates generated by Algorithm <ref>, the cross-learning function F is expected to increase at each step. Notice that, as the constant γ_F (which determines the lower bound) depends on the step size of the gradient step η^k, the CDKOMP compression budget β and the and the batch size b_U_i, it can be arbitrarily selected in order to ensure γ_F>0. Next, we use the result of Lemma <ref> to show that the expected number of iterations K needed to meet the stopping condition given by equation (<ref>) is necessarily upper bounded.
  
  Consider the iterates 𝐡^K generated by Algorithm <ref> when satisfying the stopping condition given by (<ref>), i.e., ⟨∇̂_h_i U_i (h_i^K), (h-h_i^K)⟩≤α. Under Assumptions <ref>-<ref>, given initial policies h^0, the expected number of the iterations K needed to reach the stopping condition (<ref>) is upper bounded by
  
      [K] ≤[F(h^K)-F(h^0)]/γ_F.
  
  where the constant γ_F is given by Lemma <ref>.
  
  
  See Appendix <ref>.
  
  
  By virtue of Lemma <ref>,  Algorithm <ref> is guaranteed to stop after a finite number of iterations. By definition,  when the algorithm stops at iterate K, the resulting policies 𝐡^K  meet the conditions in (<ref>). Recall that these conditions are given with respect to the stochastic unbiased estimate of the gradient, ∇̂_h_i U_i. In order to guarantee that the policies  𝐡^K are an α-FOSP of problem  (<ref>) we need to guarantee the conditions of Definition <ref>, which involves the deterministic gradient ∇_h_i U_i. In Theorem <ref> we state  that these conditions are guaranteed with high probability.
  
   
  Consider the iterates generated by Algorithm <ref>. Under Assumptions <ref>-<ref>, the set of policies 𝐡^K generated at the stopping time is an α-FOSP of problem (<ref>) with high probability. Namely, ∀ h ∈
  	
      ( max_i ∈{1,…,N }⟨∇_h_i U_i (h_i^K), (h-h_i^K) ⟩≤α' ) 
      	≥ 1-δ
  
  	where α'=α + 2ϵmax_i ∈{1,…,N }σ_U_i√(1/δ b_U_i).
  
  
  See Appendix <ref>.
  
  
  This result guarantees the convergence of Algorithm <ref>. There are several elements to take into consideration regarding the point at which it converges. The approximation α' deviates from α by the proximity factor ϵ of cross-learning, the high probability guarantee 1-δ,  and the bound given by Assumption <ref>, which can be made arbitrarily small by increasing the batch size b_U_i.
   
  
  
  § NUMERICAL RESULTS
  
  
  
  
  To evaluate the performance of our proposed cross-learning methodology, we resort to a continuous navigation problem with obstacles. We consider the  robot model shown in Figure <ref>. Following this model, the state of the agent is given by s=(d_o,ϕ_o,d_g,ϕ_g,ϕ_obs); where d_o and d_g are the distances between the agent and the obstacle and goal, respectively; ϕ_o and ϕ_g are the angles between the agent and the obstacle and the goal; and ϕ_obs is the angle of occlusion of the obstacle. Real-valued actions  (ż,ψ̇) represent  the radial and angular velocity of the agent, respectively. Furthermore, we only consider positive ż actions. The system MDP is formed by the  following dynamics
  
      x_t+1   =x_t+T_s ż_t cos(ψ_t), 
       
      y_t+1   =y_t+T_s ż_t sin(ψ_t), 
      ψ_t+1   =ψ_t+T_s ψ̇_̇ṫ,
  
  where T_s ∈^+ is the time step and both x and y are the cardinal points of the agent's state measured from the point (0,0). Furthermore, for each task, the agent takes actions from a Gaussian distribution with covariance Σ=(0.05,0.05). The mean of this Gaussian distribution is given by a policy formed by the linear combination of Gaussian kernels which are non-symmetric, and their covariance matrix is given by Σ_κ=(1, π/5, 1, π/5, π/10). The tasks over which the agent will train correspond to navigating environments with different types of obstacles. For all tasks, a collision to an obstacle results in a negative reward r(s,a)=-100. Otherwise  the reward is mostly given by the distance to goal, specifically  r(s,a)=10-10||d_g||_2. The starting point of the agent is randomly drawn from [0 ,10]× [0,10] in the absolute x × y axes of the environment. Furthermore, the time step in the MDP dynamics is selected to be T_s=0.5. Other parameters of the system are a discount factor of γ=0.9, a fixed step size of η=0.1. A batch version of the stochastic gradient in Algorithm <ref> is computed averaging 4 samples  per gradient ascent step. Furthermore, to avoid memory explosion an upper bound in the model order is set at 400 kernels.
  
  
  
   §.§ Navigation with a Single Obstacle
  
  
  
  In order to study the problem of learning multiple tasks, we consider three  scenarios with obstacles that differ in positions and radius. Specifically the obstacles are centered at c_1=(7,2)  with radius r_1=0.5 for the first task, c_2=(2,2) with r_2=1 for the second task and c_3=(7,7) with r_3=2 for the third task. We consider five policies which are trained in these scenarios. First, we consider the three policies agnostically trained for each specific task, without considering the data collected by the other agents. Then, we also consider an average policy over all tasks (equivalent to a cross-learning policy with ϵ=0, and a cross-learning policy with ϵ=3.
  
  
  
  For evaluation we use the environments shown in Fig. <ref>. We sample trajectories to illustrate the behavior of each policy when facing an obstacle with the starting point set at s_=[0.5,1.5] and the goal at s_=[5,6]. Figure <ref> shows a circular obstacle centered at (x_,y_)=(2.5,3.5). Figure <ref> shows an ellipse obstacle also centered at (x_,y_)=(2.5,3.5), but elongated along the y-axis. Specifically, the ellipse is defined by ((x-x_)/α_x)^2+((y-y_)/α_y)^2≤ 1, with (α_x,α_y)=(0.5,2).
  
  Overall, all policies are capable of avoiding the circular obstacle in Fig. <ref>. However, the policies trained for a larger radius do so in a conservative way, the more conservative the larger their training radius. Furthermore, as expected, the policy trained for the same radius r=0.5 achieves the best performance among those trained by the agnostic agents. However the cross-learned policy with ϵ=3 obtains the best overall performance. This is credited to training on a larger dataset, given the ability of the cross-learning algorithm to combine the data collected by all agents during the process. In contrast, the average policy, given by ϵ=0 crashes against the obstacle. In the case of the ellipse obstacle shown in Fig. <ref>,  not only the average policy (ϵ=0) crashes, but also the one trained for a smaller circular radius of r=0.5, as it is uncapable of steering around the ellipse. The other agnostic agents trained for larger radius (r=1 and r=2) reach the goal but in an excessively conservative way. Similar to the circle case, the policy trained for a larger radius (r=2) does so in a more conservative manner.
  
  
  
  
  
  Note that setting ϵ=0 forces consensus on the policies, and this is  too restrictive. Alternatively, with ϵ>0, each agent trains a different policy that adapts better to the data that it is collecting, and in this example, to adapt to a different radius. Policies are bound together by the constraint, so that the data collected by all agents are combined by the cross-learning algorithm. This data combination allows an agent to easily adapt to an object not seen during training. However, if ϵ is too large, the cross-learning constraint becomes inactive and the agents are agnostic of each other and the common policy g becomes undetermined (cf. (<ref>)).    
  
  
  A more qualitative look at the behavior of the different policies can be gained by looking at the cost obtained during training. This is shown in Figure <ref>, where we have plotted the absolute value of the average cost over the training iterations, with cost=-reward. The average cost has been obtained after 500 independent trials. We plot three different figures, one for each of the training environments, r=0.5, r=1, and r=2. First, notice that out of the agnostic policies, the one specifically trained for its respective environment outperforms all the rest. For example, in Fig. <ref>, corresponding to the scenario with a radius r=0.5, the agnostic policy trained for r=0.5, outperforms the rest. This behavior is repeated in Fig. <ref> and <ref>. However, agnostic policies do not perform well in different scenarios to the one being trained on. For example, the policy trained for r=0.5, performs the worst for the scenario with radius r=2 (Fig. <ref>). This is validated by our previous findings in Fig. <ref>, as the policy trained with radius r=0.5 has trouble maneuvering around bigger obstacles. More importantly, the cross-learned policy with ϵ=3 performs comparably well to the task-specific policy in each case, even performing better in the case of r=2 (Fig. <ref>). In contrast, as observed before, the average policy (ϵ=0) underperforms for all the scenarios.
  
  
  
  The adaptability of the cross-learned policy can be seen more clearly in Figure <ref>. In this figure, we plot the absolute value of the average cost over the three tasks. Overall, any of the agnostically trained policies, if averaged over tasks, performs similarly. This is also the case of the average policy (ϵ=0). In contrast, the cross-learned policy (ϵ=3)  outperforms the rest of the policies.
  
  
  
   §.§ Navigation with Multiple Obstacles
  
  
  
  Recall that the robot model introduced in Fig. <ref> operates on a local frame. Thus, we can use the training on an individual obstacle and goal to study the generalization capabilities of our proposed method to multiple goals and obstacles of different shapes and sizes. To this end, we consider the scenario shown in Figure <ref>. The same policies trained in the environment described in the previous section are evaluated in this new environment. The agents start at [0.5,1.5] and navigate to a series of subsequent objectives in the following order _1=[5,6], _2=[5.5,1.5], and _3=[11,5]. The state of the agent is determined by the current goal and the closest obstacle.
  
  First, notice that as in the single goal and obstacle navigation case of Fig. <ref>, the average policy (ϵ=0) fails to navigate, crashing against the first obstacle on its way to the first goal. Compared to this, the agnostically trained policies perform slightly better. The agnostic policy for r=0.5  performs well when avoiding the obstacles with similar small radius, but then crashes to the larger ellipse. The policy trained for the larger radius (r=2) avoids obstacles in a more conservative way, which ultimately prevents it from navigating to the last goal, overshooting and then crashing into the ellipse as well. However, the policy trained with the obstacle of radius r=1 succeeds in navigating to through all the goal, even though it does so in a conservative way. Compared to all of the agnostically trained policies, the cross-learned policy (ϵ=3) navigates faster through the environment, achieving all the goals and avoiding all the obstacles.
  
  	
  
  
  
  § CONCLUSIONS
  
  
  
  We have introduced cross-learning as a framework for training policies in multiple tasks jointly. Posed as a constrained optimization problem, the learning strategy  maximizes  task specific  rewards while  coupling the policies together. The cross-learning policies live in between agnostic policies that train for their individual tasks separately, and   consensus policies that train for  average rewards. In between these two extremes, the policies gain the capability of learning to maximize separate rewards  but sharing training  data acquired across tasks.  This capability makes the cross-learning policies successful at two novel aspects.  It produces a central policy   that can be used as starting point to adapt quickly to one of the tasks trained for, in a situation when the agent does not know which task is currently facing. Moreover, this central policy generalizes better to tasks related but different to those seen during training. These improvements are obtained through a projected stochastic gradient ascent algorithm that incorporates state and reward data   sequentially, converging with high probability to a near optimal policy.   We have studied the properties of the required projection step, finding a relaxed formulation with a closed-form solution, useful when the computational resources are limited, and added an extra projection to curtail the number of kernels  in order to avoid memory explosion. Numerical results over  navigation tasks have shown that  policies can avoid obstacles not trained for, and can manage through environments with obstacles of multiple shapes.
  
  
  
  
  
  
  
  § COMMON DICTIONARY KERNEL ORTHOGONAL MATCHING PURSUIT (CDKOMP)
   
  
  In this appendix, we cover the required procedure to reduce the policies to a lower dimensional space. Starting by setting all the N policies at iteration k=0 to zero, i.e. h^0_i= 0, each stochastic gradient ascent iteration results in new policies
  
      h̅_i^k=h_i^k+η^k ∇̂_h_i U_i (h_i^k),    i=1,…,N,
  
  where η^k ∈ (0,1) is the step size and ∇̂_h_iU_i(h_i^k) are obtained by the unbiased estimate for the gradient of U_i given by Algorithm <ref>. For the matter of Algorithm <ref>, cross-learning policy g can be considered as one policy whose gradient is always 0, namely g̅^k=g^k. Herein, cross-learning policy g will be treated as any other policy.
  
   Policies h_i can be represented by their respective dictionaries by rewriting η^k ∇̂_h_iU_i(h_i^k,·)=w_i,kκ(s_i,k,·). Hence, resulting at the k-th iteration in the dictionary D_h_i^k = { s_i,1,…,s_i,M_i} and weights W_h_i^k={w_i,1,…,w_i,M_i}. A priori, each policy h_i may have a different amount of kernels in their dictionaries, meaning that M_i ≠ M_j, for i≠ j. However, this cannot happen because of Assumption <ref>, which states that all dictionaries should only differ in one kernel, which is the last kernel obtained via the unbiased estimate Algorithm <ref>. Thus, at the k-th iteration, all {h_i^k},g^k  policies must have L^k kernels and the policy h̅_i^k produced after the gradient ascent step, L^k+1 kernels. Notice that the gradient ascent step adds no kernel to g^k. Hence, when reducing the complexity of the dictionary, an element is either eliminated from all dictionaries or not eliminated from any of them.
  
  After obtaining an unbiased estimate for the gradient of U_i via Algorithm <ref> and computing the gradient ascent, we perform the cross-learning projection (<ref>) or its relaxed version (<ref>) and obtain the next policy, 
  
      ({h̃_i^k+1},g̃^k+1)=_[{ h_i^k+η^k ∇̂_h_iU_i(h_i^k) },g^k].
  
  In this case, after the projection, all policies h̃_i^k+1 and g̃^k+1 will have the same number of kernels L_k+1=L_k+N. If no kernel is eliminated from the dictionary, at time k, the N+1 policies will each have k N number of kernels. This ultimately can result in computational problems as k increases. Thus, we aim to find a way to reduce the number of kernels while maintaining their function approximation capabilities. Hence, we compute the approximation error of eliminating each element in the dictionary. Abusing notation, we omit the step k in the notation, as what follows is independent from the iteration step and we will refer to the cross-learning policy h_N+1=g. Defining h̃_i by dictionary D_h̃_i={s_i,1,…,s_i,L} and the vector of stacked weights w_h̃_i=[w_i,1^T,…,w_i,L^T]^T, we refer to h̃_i^j with j ∈{1,…,L} as the policy that has the same kernel centers as D_h̃_i but not element s_j. Then, we can compute the minimum distance between h_i and h_i^j  as, follows
  
      e(j,h̃_i)   =𝐰_h̃_i^j∈^L × Pmin||h̃_i-h̃_i^j||^2_
         =𝐰_h̃_i^T 𝐊_D_h̃_i, D_h̃_i𝐰_h̃_i
         +𝐰_h̃_i^j∈^L × Pmin𝐰_h̃_i^j^T 𝐊_D_h̃^j_i, D_h̃^j_i𝐰_h̃^j_i 
      	- 2 𝐰_h̃_i^j^T 𝐊_D_h̃^j_i, D_h̃_i𝐰_h̃_i
  
  by substituting h̃_i and h̃_i^j by their weights and dictionary representation and defining the block matrices 𝐊_(·,·) whose (l,m)-th blocks of size p × p are Κ (s_l,s_m), with s_l ,s_m ∈D_h̃_i in 𝐊_D_h̃_i, D_h̃_i, s_l ∈D_h̃_i^j,  s_m ∈D_h̃_i in 𝐊_D_h̃^j_i, D_h̃_i and s_l ,s_m ∈D_h̃^j_i in 𝐊_D_h̃^j_i, D_h̃^j_i. Notice that element 𝐰_h̃_i^T 𝐊_D_h̃_i, D_h̃_i𝐰_h̃_i is constant in the minimization, as it does not depend of 𝐰_h̃^j_i. Furthermore, the previous problem is a least-squares which close form solution can be given by 
  
      𝐰_h̃_i^j^⋆=
      𝐊_D_h̃^j_i, D_h̃_i^j^†𝐊_D_h̃^j_i, D_h̃_i𝐰_h̃_i,
  
  where (·)^† denotes the Moore-Penrose pseudo-inverse. After arguing that the policies share the kernel centers, and ergo share their dictionaries D_h̃_i, we have obtained a closed-form solution to the error of taking one element out of the dictionary. Now, we can evaluate which the kernel eliminations renders the smallest error in all of the policies. First, we must compute the largest error per element in all of the policies,
  
      ẽ(j)=i ∈{1,…,N}max   e(j,h̃_i) ,
  
  where e(j,h̃_i) is the error obtained by equation (<ref>). Hence, ẽ(j) denotes the maximum error in all policies if the j-th kernel were to be eliminated. This means that if ẽ(j) is small, the error of eliminating kernel j in all policies is small. Now, we need to compute which element renders the smallest error. Namely,
  
      ẽ^⋆=j ∈{1,…,L}min  ẽ(j).
  
  
  
  
  As mentioned earlier, our goal is to eliminate an element from the dictionary, as long as the error that we incur is upper bounded by a value β. Hence, if ẽ^⋆<β, element j^⋆, being the one that verifies ẽ^⋆=ẽ(j^⋆) is removed. The final result of this pruning process are N functions h^k+1_i that are less than β close to the functions before the pruning procedure and are represented by the same or less elements. This results in the Common Dictionary Kernel Orthogonal Matching Pursuit (CDKOMP) procedure, a summarized description of which is shown in Algorithm <ref>. This process can be equivalently interpreted as a projection to a RKHS of lower dimension.  If we denote by D_h̃_i the dictionary of the output of Algorithm (<ref>), then the resulting policies h_i^k+1 can be interpreted as, the projection
  
      ({h^k+1_i},g^k+1)=__ [ _[{h_i^k +η^k ∇̂_h_i U_i (h_i^k)}, g^k  ] ].
  
  Now, after showing that the pruning  procedure can be seen as a projection over a lower dimension space, we show that this projection is equivalent to running a biased projected gradient ascent. 
  
  
  	The projection to pruned dictionary step in Algorithm <ref> is equivalent to running biased projected gradient ascent, with bias
  
      {b^k_i}=__    [ _[{h^k_i +η^k ∇̂_h_i U_i (h^k_i)},g^k ] ]  
         - _[ {h_i^k + η^k ∇̂_h_i U_i (h^k_i) },g^k ]
  
  bounded by the compression budget, i.e., b_i^k≤β for all k>0,i=1,…,N+1.
  
  
  	Note that following the procedure in Algorithm <ref>, the projection to the dictionary of reduced dimension is given by (<ref>). Adding and subtracting the argument of this projection, that is _[{h^k_i + η^k ∇̂_h_i U_i  (h^k_i)},g^k ], it is possible to write the resulting policies h_i^k+1 as
  	
      ({h_i^k+1},g^k+1)=__ [ _[ {h^k_i +η^k ∇̂_h_i U_i  (h^k_i) },g^k] ] 
       
      	- _[{h^k_i +η^k ∇̂_h_i U_i  (h^k_i) },g^k]
      
      	+ _[ {h^k_i +η^k ∇̂_h_i U_i  (h^k_i)},g^k ].
  
  Then, simply using the definition of the bias b^k_i, given by equation (<ref>), the previous expression can we written as
  		
      ({h^k+1_i},g^k+1)=_[ {h^k_i + η^k ∇̂_h_i U_i  (h^k)},g^k ] + {b^k_i}.
  
  	Using the compression budget imposed in Algorithm <ref>, it follows that |b^k_i| ≤β for all k>0,i=1,…,N+1.
  
  
  
  
  § PROOF OF LEMMA <REF>
   
  
  Let us define the difference between the policy vector h at iteration k and k+1 by Δh ^k=h^k+1-h^k=[h^k+1_1-h^k_1,…,h^k+1_N-h^k_N]. Let us also define the internal product between two policy vectors ⟨h^k+1, h^k⟩=∑_i=1^N ⟨ h^k+1_i,h^k_i⟩_, which induces the norm ||h||=√(∑_i=1^N ||h_i ||_^2).
  
  Applying the Mean Value Theorem in each policy h_i, for f_i=λ_i h^k+1_i+(1-λ_i)h_i^k, with λ_i ∈ [0,1] and i=1,…,N, we have that
  
      F(h^k+1)-F(h^k)=⟨∇_h F (𝐟), Δh^k ⟩,
  
  where f=[f_1,…,f_N]. Adding and subtracting the stochastic gradient of equation (<ref>), i.e., ⟨∇̂_h F (𝐟), Δh^k ⟩ we have
  
      F   (h^k+1)-F(h^k)
         =⟨∇̂_h F(h^k), Δh^k ⟩ +⟨∇_h F(f) - ∇̂_h F(h^k) , Δh^k ⟩
         =∑_i=1^N⟨∇̂_h_i U_i(h_i^k), Δ h_i^k ⟩ +⟨∇_h F(f) - ∇̂_h F(h^k) , Δh^k ⟩.
  
  Using the fact that the stopping condition equation (<ref>) is not met for k<K, we can define j as the index at which the maximum internal product j=_i ⟨∇̂_h_i U_i(h_i^k), Δ h_i^k ⟩ is obtained. By virtue of the stopping condition (<ref>) and Cauchy-Schwartz inequality we obtain, 	
  
      F(   h^k+1)-F(h^k)
         = ⟨∇̂_h_j U_j(h_j^k), Δ h_j^k ⟩+∑_i=1,i≠ j^N⟨∇̂_h_i U_i(h_i^k), Δ h_i^k ⟩
         +⟨∇_h F(f) - ∇̂_h F(h^k) , Δh^k ⟩
         ≥α +∑_i=1,i≠ j^N⟨∇̂_h_i U_i(h_i^k), Δ h_i^k ⟩
         +⟨∇_h F(f) - ∇̂_h F(h^k) , Δh^k ⟩
         ≥α-||∇̂_hF(h^k)||_ ||Δh^k|| 
         -⟨∇_h F(f)-∇̂_h F(h^k) , Δh^k ⟩.
  
  Observe that the previous inequality holds as adding the j-term to the policy vector increases its norm. Then, adding and subtracting the internal product between the deterministic gradient and the difference ∇h^k, ⟨∇_hF(h^k),Δh^k ⟩, the right hand side of the previous expression can be rewritten as, 
  
      F   (h^k+1)-F(h^k)
         ≥α-||∇_hF(h^k)|| ||Δh^k||- ⟨∇_h F(h^k) - ∇̂_h F(h^k) , Δh^k ⟩
         -⟨∇_h F(f) - ∇_h F(h^k) , Δh^k ⟩.
  
  Applying Cauchy-Schwartz inequality and explicitly rewriting the internal product between the cross-learning function as the sum of the term-wise internal products we obtain, 
  
      F(h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||-|| ∇_h F(h^k) -  ∇̂_h F(h^k) || ||Δh^k ||
         -∑_i=1^N ⟨∇_h_i U_i(f_i) - ∇_h_i U_i(h_i^k) , Δ h_i^k ⟩.
  
  Using Cauchy-Schwartz inequality and by virtue of Assumption <ref> and upper bounding the Lipschitz constants by L_max=max_i L_i the last term can be bounded by, 
  
      F(h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||-|| ∇_h F(h^k) -  ∇̂_h F(h^k) || ||Δh^k ||
         -∑_i=1^N || ∇̂_h_i U_i(f_i) - ∇_h_i U_i(h_i^k) || || Δ h_i^k ||
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||-|| ∇_h F(h^k) -  ∇̂_h F(h^k) || ||Δh^k ||
         -∑_i=1^N L_i || Δ h_i^k ||^2
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||-|| ∇_h F(h^k) -  ∇̂_h F(h^k) || ||Δh^k ||
         - L_max∑_i=1^N || Δ h_i^k ||^2.
  
  Since we defined the norm ||Δh||=(∑_i=1^N ||Δ h_i||^2_)^1/2, we can rewrite the last expression as, 
  
      F(h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||-|| ∇_h F(h^k) -  ∇̂_h F(h^k) || ||Δh^k ||
         - L_max||Δh^k||^2.
  
  Using triangle inequality over the norm of cross-learning gradients ∇̂_h F(h^k) function we can write, 
  
      F(   h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| ||Δh^k||- L_max||Δh^k||^2
         -||Δh^k ||∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) || .
  
  So far we only considered policies {h_i}_i=1^N and not the central g.
  Notice that because of how we defined the norm, expanding the policy vector with the cross-learning policy results in ||z||=||[h,g]||≥||h||. By defining the expanded policy vector z=[h,g] we can rewrite (<ref>), 
  
      F(   h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| ||Δz^k||- L_max||Δz^k||^2
         -||Δz^k ||∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) || .
  
  
  Where we have defined Δz^k=z^k+1-z^k as the difference between the expanded policy vector z^k=[h^k,g^k] and its next iteration, given by z^k+1=_[z^k+ η^k ∇̂_z F(z^k)]+b^k=_[{h^k+ η^k ∇̂_h F(h^k)},g^k]+b^k. The previous equality holds as the cross-learning function F(·) does not depend on the cross-learning policy g and thus its derivative with respect to cross-learning policy is zero, ∇_g F(·)=0. As the projection to the convex set _ is non-expansive, using the triangle inequality we can write an inequality with respect to the stochastic gradient of  the expected discounted returns U_i,
  
      ||Δz^k||   =||z^k+1-z^k|| 
         =||_ [z^k +η^k ∇̂_z F(z^k) ]+b^k - z^k|| 
         ≤ ||_ [z^k +η^k ∇̂_z F(z^k) ] - z^k||+||b^k|| 
         ≤ ||η^k ∇̂_z F(z^k)||+||b^k|| 
         = ||η^k ∇̂_h F(h^k)||+||b^k|| 
         ≤η^k|| ∇̂_h F(h^k)||+∑_i=1^N+1||b_i^k||
         ≤η^k∑_i=1^N ||∇̂_h_i U_i(h_i^k)||+√(N+1)β.
  
  With a similar procedure, in the case of the square of the norm of the expanded policy vector, ||Δz^k||^2 we can obtain an upper bound by bounding the inner product between the cross-terms as follows,
  
      ||Δz^k||^2 =||z^k+1-z^k||^2 
         = ||η^k ∇̂_h F(h^k)||^2+(N+1)β^2+2√(N+1)β||η^k ∇̂_h F(h^k)|| 
         = (||η^k ∇̂_h F(h^k)||+√(N+1)β)^2 
         ≤ 3||η^k ∇̂_h F(h^k)||^2+3(N+1)β^2.
  
  Where we used (a+b)^2≤ 3a^2+3b^2. Hence, we can apply expressions (<ref>), (<ref>) and (<ref>) to the bound in (<ref>), to obtain the following inequality
  
      F(h^k+1)-F(h^k)
         ≥α-||∇̂_hF(h^k)|| (η^k|| ∇̂_h F(h^k)||+√(N+1)β) 
         - L_max(3||η^k ∇̂_h F(h^k)||^2+3(N+1)β^2)
         -η^k∑_i=1^N ||∇̂_h_i U_i(h_i^k)||(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) ||)
         -√(N+1)β(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k)||)
         ≥α-3(N+1)β^2L_max- √(N+1)β||∇̂_hF(h^k)|| 
         - (3 (η^k)^2 L_max+η^k)|| ∇̂_h F(h^k)||^2
         -η^k∑_i=1^N ||∇̂_h_i U_i(h_i^k)||(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) ||)
         -√(N+1)β(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k)||).
  
   Observe that the square of the norm of the stochastic gradient of the cross-learning function F(·) is equal to the sum of the squares of the term-wise norm, namely,
  
      ||∇̂_hF(h^k)||^2   =||∇̂_h∑_i=1^NU_i(h_i^k)||^2
         =||[∇̂_h_1U_1(h_1^k),…,∇̂_h_NU_N(h_N^k)]^T||^2
         =∑_i=1^N ||∇̂_h_iU_i(h_i^k)||^2.
  
  Substituting (<ref>) for ||∇̂_hF(h^k)||^2 and using triangle inequality on the norm of the gradient of the cross-learning function in (<ref>) we obtain, 
  
      F(h^k+1)-F(h^k)
         ≥α-3(N+1)β^2L_max- √(N+1)β∑_i=1^N ||∇̂_h_iU_i(h_i^k)|| 
         - (3 (η^k)^2 L_max+η^k)(∑_i=1^N ||∇̂_h_iU_i(h_i^k)||^2)
         -η^k∑_i=1^N ||∇̂_h_i U_i(h_i^k)||(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) ||)
         -√(N+1)β(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k)||).
  
  We can further add and subtract the deterministic gradient of the expected discounted returns ∇_h_i U_i(h_i^k) to the two terms that refer to the norm of the stochastic gradient of the expected discounted returns ||∇̂_h_i U_i(h_i^k)|| of equation (<ref>) and using the triangle inequality we obtain,
  
      F(h^k+1)-F(h^k)
         ≥α-3(N+1)β^2L_max
         -√(N+1)β∑_i=1^N ||∇̂_h_iU_i(h_i^k)-∇_h_iU_i(h_i^k)|| 
         - √(N+1)β∑_i=1^N ||∇_h_iU_i(h_i^k)|| 
         - (3 (η^k)^2 L_max+η^k)(∑_i=1^N ||∇̂_h_iU_i(h_i^k)||^2)
         -η^k∑_i=1^N ||∇_h_i U_i(h_i^k)||(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) ||)
         -η^k(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k) ||)^2
         -√(N+1)β(∑_i=1^N || ∇_h_i U_i(h_i^k) -  ∇̂_h_i U_i(h_i^k)||).
  
  Then, taking the expectation on both side and using Assumptions <ref>, <ref> and <ref> it yields
  
      [F(h^k+1)-F(h^k)]
         ≥α-3(N+1)β^2L_max- √(N+1)β∑_i=1^Nσ_U_i/√(b_U_i)
         - √(N+1)β∑_i=1^N μ_i - (3 (η^k)^2 L_max+η^k)(∑_i=1^N B_U_i^2)
         -η^k∑_i=1^N μ_i(∑_i=1^N σ_U_i/√(b_U_i))-η^k(∑_i=1^N σ_U_i/√(b_U_i))^2
         -√(N+1)β(∑_i=1^N σ_U_i/√(b_U_i)).
  
  Thus, by defining η=sup_k η_k and γ_F to be
  
      γ_F=α-3(N+1)β^2L_max- √(N+1)β∑_i=1^Nσ_U_i/√(b_U_i)
         - √(N+1)β∑_i=1^N μ_i - (3 η^2 L_max+η)(∑_i=1^N B_U_i^2)
         -η∑_i=1^N μ_i(∑_i=1^N σ_U_i/√(b_U_i))-η(∑_i=1^N σ_U_i/√(b_U_i))^2
         -√(N+1)β(∑_i=1^N σ_U_i/√(b_U_i)).
  
  we obtain the desired result.
  
  
  
  
  § PROOF OF LEMMA <REF>
   
  
  
  	Given the iterates h^K and the initial policies h^0, we can express the difference [F(h^K)-F(h^0)], as the summation over difference of iterates. That is,
  	
      [F(h^K)-F(h^0)]=[∑_k=1^K F(h^k)-F(h^k-1)].
  
  	Then, taking the expectation with respect to the final iterate at t=K, we have 
  	
      [F(h^K)-F(h^0)]=_K[[∑_k=1^K F(h^k)-F(h^k-1)|K]].
  
  	Expanding the outermost expectation and applying the result of Lemma <ref> it follows, 
  	
      [F(h^K)-F(h^0)]=   ∑_t=0^∞[∑_k=1^t F(h^k)-F(h^k-1)]  (K=t) 
      ≥   γ_F ∑_t=0^∞t   (K=t) 
      ≥   γ_F [K].
  
  	Rearranging the terms of the previous inequality gives us the desired result.
  
  
  
  
  
  § PROOF OF THEOREM <REF>
   
  
   	
  	We begin with the inner product ⟨∇_h_i U_i (h_i^K), (h-h_i^K)⟩ and then add and subtract its stochastic counterpart ⟨∇̂_h_i U_i (h_i^K), (h-h_i^K)⟩ to obtain,
  	
      ⟨∇_h_i U_i    (h_i^K), (h-h_i^K)⟩ =⟨∇̂_h_i U_i (h_i^K), (h-h_i^K)⟩
            +⟨(∇_h_i U_i (h_i^K)-∇̂_h_i U_i (h_i^K)), (h-h_i^K)⟩.
  
  	By construction, policies h^K_i and any h ∈ must be ϵ-close to the cross-learned policy g hence ||h_i^k-h||≤2ϵ, ∀ h ∈, then using the stopping time condition (<ref>) and the Cauchy-Schwartz inequality, we can rewrite the previous expression as
  	
      ⟨∇_h_i U_i     (h_i^K), (h-h_i^K)⟩
         ≤α+ 2 ϵ  ||∇̂_h_i U_i (h_i^K)-∇_h_i U_i(h_i^K)||
         ≤α+ 2 ϵmax_i ∈{1,…,N } ||∇̂_h_i U_i (h_i^K)-∇_h_i U_i(h_i^K)||.
  
  	Since the right hand side of (<ref>) does not depend on h or i, then by computing the maximum over h it holds that
  	
      max_h ∈⟨∇_h_i U_i (h_i^K), (h-h_i^K)⟩
           ≤α + 2 ϵmax_i ∈{1,…,N } ||∇̂_h_i U_i (h_i^K)-∇_h_i U_i(h_i^K)||.
  
  	Using Markov's inequality together with Assumption <ref>, it yields,
  	
      (max_i ∈{1,…,N }||∇̂_h_i U_i     (h_i^K)-∇_h_i U_i(h_i^K)||≤ξ) 
           ≥ 1-1/ξ^2max_i ∈{1,…,N }σ_U_i^2/b_U_i.
  
  	Hence, combining (<ref>) and (<ref>) it follows that
  	
      ( max_i ∈{1,…,N }⟨∇_h_i  U_i (h_i^K),     (h-h_i^K)⟩≤α + 2ϵξ) 
         ≥ 1-1/ξ^2max_i ∈{1,…,N }σ_U_i^2/b_U_i.
  
  	Then we can define the following constants, α'=α + 2ϵξ and δ=1/ξ^2max_i ∈{1,…,N }σ_U_i^2/b_U_i to obtain
  	
      ( max_i ∈{1,…,N }⟨∇_h_i U_i (h_i^K), (h-h_i^K) ⟩≤α' ) 
      	≥ 1-δ
  	
  	where we can also rearrange terms to obtain the value α'=α + 2ϵmax_i ∈{1,…,N }σ_U_i√(1/δ b_U_i), which is the intended result. 
  
  
  
  
  
  IEEEtran
  
  
  [
      < g r a p h i c s >
  ]
    Juan Cerviño received the B.Sc. degree in electrical engineering from the Universidad de la República Oriental del Uruguay, Montevideo, in 2018. He is a PhD student in the Department of Electrical and Systems Engineering at the University of Pennsylvania since 2019. Juan's current research interests are in machine learning, optimization and control.
  
  
  [
      < g r a p h i c s >
  ]Juan Andrés Bazerque received the B.Sc. degree in electrical engineering from Universidad de la República (UdelaR), Montevideo, Uruguay, in 2003, and the M.Sc. and Ph.D. degrees from the Department of Electrical and Computer Engineering, University of Minnesota (UofM), Minneapolis, in 2010 and 1013 respectively.
   Since 2015 he is an Assistant Professor with the  Department of Electrical Engineering  at UdelaR. His current research interests include  stochastic optimization and  networked systems, focusing on reinforcement learning, graph signal processing, and power systems optimization and control. 
  Dr. Bazerque is the recipient of the UofM's Master Thesis Award 2009-2010, and co-reciepient of the best paper award at the 2nd International Conference on Cognitive Radio Oriented Wireless Networks and Communication 2007.   
   
  
  [
      < g r a p h i c s >
  ]
    Miguel Calvo-Fullana received his B.Sc. degree in electrical engineering from the Universitat de les Illes Balears (UIB), in 2010 and the M.Sc. and Ph.D. degrees in electrical engineering from the Universitat Politècnica de Catalunya (UPC), in 2013 and 2017, respectively. From September 2012 to July 2013 he was a research assistant with Nokia Siemens Networks (NSN) and Aalborg University (AAU). From December 2013 to July 2017, he was with the Centre Tecnològic de Telecomunicacions de Catalunya (CTTC) as a research assistant. Since September 2017, he is a postdoctoral researcher at the University of Pennsylvania. His research interests lie in the broad areas of learning and optimization for autonomous systems. In particular, he is interested in multi-robot systems with an emphasis on wireless communication and network connectivity. He is the co-recipient of best paper awards at GlobalSIP 2015, ICC 2015, and ICASSP 2020.  
  
  
  [
      < g r a p h i c s >
  ]
      Alejandro Ribeiro received the B.Sc. degree in electrical engineering from the Universidad de la Republica Oriental del Uruguay, Montevideo, in 1998 and the M.Sc. and Ph.D. degree in electrical engineering from the Department of Electrical and Computer Engineering, the University of Minnesota, Minneapolis in 2005 and 2007. From 1998 to 2003, he was a member of the technical staff at Bellsouth Montevideo. After his M.Sc. and Ph.D studies, in 2008 he joined the University of Pennsylvania (Penn), Philadelphia, where he is currently Professor of Electrical and Systems Engineering. His research interests are in the applications of statistical signal processing to collaborative intelligent systems. His specific interests are in wireless autonomous networks, machine learning on network data and distributed collaborative learning. Papers coauthored by Dr. Ribeiro received the 2014 O. Hugo Schuck best paper award, and paper awards at CDC 2017, SSP Workshop 2016, SAM Workshop 2016, Asilomar SSC Conference 2015, ACC 2013, ICASSP 2006, and ICASSP 2005. His teaching has been recognized with the 2017 Lindback award for distinguished teaching and the 2012 S. Reid Warren, Jr. Award presented by Penn’s undergraduate student body for outstanding teaching. Dr. Ribeiro is a Fulbright scholar class of 2003 and a Penn Fellow class of 2015.    
  
  
  
  