Mohammad Gheshlaghi Azar

Alessandro Lazaric

Emma Brunskill

Regret Bounds for Reinforcement Learning with Policy Advice

In some reinforcement learning problems an agent may be provided with a set of input policies, perhaps learned from prior experience or provided by advisors. We present a reinforcement learning with policy advice (RLPA) algorithm which leverages this input set and learns to use the best policy in the set for the reinforcement learning task at hand. We prove that RLPA has a sub-linear regret of O( √ T ) relative to the best input policy, and that both this regret and its computational complexity are independent of the size of the state and action space. Our empirical simulations support our theoretical analysis. This suggests RLPA may offer significant advantages in large domains where some prior good policies are provided.

Introduction

In reinforcement learning an agent seeks to learn a high-reward policy for selecting actions in a stochastic world without prior knowledge of the world dynamics model and/or reward function. In this paper we consider when the agent is provided with an input set of potential policies, and the agent's objective is to perform as close as possible to the (unknown) best policy in the set. This scenario could arise when the general domain involves a finite set of types of RL tasks (such as different user models), each with known best policies, and the agent is now in one of the task types but doesn't know which one. Note that this situation could occur both in discrete state and action spaces, and in continuous state and/or action spaces: a robot may be traversing one of a finite set of different terrain types, but its sensors don't allow it to identify the terrain type prior to acting. Another example is when the agent is provided with a set of domain expert defined policies, such as stock market trading strategies. Since the agent has no prior information about which policy might perform best in its current environment, this remains a challenging RL problem.

Prior research has considered the related case when an agent is provided with a fixed set of input (transition and reward) models, and the current domain is an (initially unknown) member of this set [START_REF] Dyagilev | Efficient reinforcement learning in parameterized models: Discrete parameter case[END_REF][START_REF] Diuk | The adaptive k-meteorologists problem and its application to structure learning and feature selection in reinforcement learning[END_REF][START_REF] Brunskill | Bayes-optimal reinforcement learning for discrete uncertainty domains[END_REF]. This actually provides the agent with more information than the scenario we consider (given a model we can extract a policy, but the reverse is not generally true), but more significantly, we find substantial theoretical and computational advantages from taking a modelfree approach. Our work is also closely related to the idea of policy reuse [START_REF] Fernández | Probabilistic policy reuse in a reinforcement learning agent[END_REF],

where an agent tries to leverage prior policies it found for past tasks to improve performance on a new task; however, despite encouraging empirical performance, this work does not provide any formal guarantees. Most similar to our work is Talvitie and Singh's [START_REF] Talvitie | An experts algorithm for transfer learning[END_REF] AtEase algorithm which also learns to select among an input set of policies; however, in addition to algorithmic differences, we provide a much more rigorous theoretical analysis that holds for a more general setting.

We contribute a reinforcement learning with policy advice (RLPA) algorithm. RLPA is a model-free algorithm that, given an input set of policies, takes an optimism-under-uncertainty approach of adaptively selecting the policy that may have the highest reward for the current task. We prove the regret of our algorithm relative to the (unknown) best in the set policy scales with the square root of the time horizon, linearly with the size of the provided policy set, and is independent of the size of the state and action space. The computational complexity of our algorithm is also independent of the number of states and actions. This suggests our approach may have significant benefits in large domains over alternative approaches that typically scale with the size of the state and action space, and our preliminary simulation experiments provide empirical support of this impact.

Preliminaries

A Markov decision process (MDP) M is defined as a tuple S, A, P, r where S is the set of states, A is the set of actions, P : S × A → P(S) is the transition kernel mapping each state-action pair to a distribution over states, and r : S × A → P([0, 1]) is the stochastic reward function mapping state-action pairs to a distribution over rewards bounded in the [0, 1] interval. 3 A policy π is a mapping from states to actions. Two states s i and s j communicate with each other under policy π if the probability of transitioning between s i and s j under π is greater than zero. A state s is recurrent under policy π if the probability of reentering state s under π is 1. A recurrent class is a set of recurrent states that all communicate with each other and no other states. Finally, a Markov process is unichain if its transition matrix consists of a single recurrent class with (possibly) some transient states [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Chap. 8].

We define the performance of π in a state s as its expected average reward

µ π (s) = lim T →∞ 1 T E T t=1 r(s t , π(s t )) s 0 = s , (1)
where T is the number of time steps and the expectation is taken over the stochastic transitions and rewards. If π induces on M a unichain Markov process, 4 then µ π (s) is constant over all the states s ∈ S, and we can define the bias function λ π such that

λ π (s) + µ π = E r(s, π(s)) + λ π (s ′ ) . (2)
Its corresponding span is sp(λ π ) = max s λ π (s) -min s λ π (s). The bias λ π (s) can be seen as the total difference between the reward of state s and average reward. In reinforcement learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] an agent does not know the transition P and/or reward r model in advance. Its goal is typically to find a policy π that maximizes its obtained reward. In this paper, we consider reinforcement learning in an MDP M where the learning algorithm is provided with an input set of m deterministic policies Π = {π 1 , . . . , π m }. Such an input set of policies could arise in multiple situations, including: the policies may represent near-optimal policies for a set of m MDPs {M 1 , . . . , M m } which may be related to the current MDP M ; the policies may be the result of different approximation schemes (i.e., approximate policy iteration with different approximation spaces); or they may be provided by m advisors. Our objective is to perform almost as well as the best policy in the input set Π on the new MDP M (with unknown P and/or r).

Our results require the following mild assumption:

Assumption 1 There exists a policy π + ∈ Π, which induces a unichain Markov process on the MDP M , such that the average reward µ + = µ π + ≥ µ π (s) for any state s ∈ S and any policy π ∈ Π. We also assume that sp(λ π + ) ≤ H, where H is finite constant. 5This assumption trivially holds when the optimal policy π * is in the set Π. Also, in those cases that all the policies in Π induce some unichain Markov processes the existence of π + is guaranteed. 6A popular measure of the performance of a reinforcement learning algorithm over T steps is its regret relative to executing the optimal policy π * in M . We evaluate the regret relative to the best policy π + in the input set Π,

∆(s) = T µ + - T t=1 r t , (3)
where r t ∼ r(•|s t , a t ) and s 0 = s. We notice that this definition of regret differs from the standard definition of regret by an (approximation) error T (µ * -µ + ) due to the possible sub-optimality of the policies in Π relative to the optimal policy for MDP M . Further discussion on this definition is provided in Sec 8.

Algorithm

In this section we introduce the Reinforcement Learning with Policy Advice (RLPA) algorithm (Alg. 1). Intuitively, the algorithm seeks to identify and use the policy in the input set Π that yields the highest average reward on the Algorithm 1 Reinforcement Learning with Policy Advice (RLPA)

Require: Set of policies Π, confidence δ, span function f 1: Initialize t = 0, i = 0 2: Initialize n(π) = 1, µ(π) = 0, R(π) = 0 and K(π) = 1 for all π ∈ Π 3: while t ≤ T do 4:

Initialize ti = 0, Ti = 2 i , Πi = Π, H = f (Ti) 5: i = i + 1 6: while ti ≤ Ti & Πi = ∅ do (run trial) 7: c(π) = ( H + 1) 48 log(2t/δ) n(π) + H K(π) n(π) 8: B(π) = µ(π) + c(π) 9: π = arg maxπ B(π) 10: v( π) = 1 11: while ti ≤ Ti & v( π) < n( π) & 12: µ( π) -R( π) n( π)+v( π) ≤c( π)+( H +1) 48 log(2t/δ) n( π)+v( π) + H K( π) n( π)+v( π) do 13:
(run episode) 14:

t = t + 1, ti = ti + 1 15:
Take action π(st), observe st+1 and rt+1 16:

v( π) = v( π) + 1 , R( π) = R( π) + rt+1 17:
end while 18:

K( π) = K( π) + 1 19: if µ( π) -R( π) n( π)+v( π) > c( π) + ( H +1) 48 log(2t/δ) n( π)+v( π) + H K( π) n( π)+v( π) then 20: Πi = Πi -{ π} 21: end if 22: n( π) = n( π) + v( π) , µ( π) = R( π) n( π)
23: end while 24: end while current MDP M . As the average reward of each π ∈ Π on M , µ π , is initially unknown, the algorithm proceeds by estimating these quantities by executing the different π on the current MDP. More concretely, RLPA executes a series of trials, and within each trial is a series of episodes. Within each trial the algorithm selects the policies in Π with the objective of effectively balancing between the exploration of all the policies in Π and the exploitation of the most promising ones. Our procedure for doing this falls within the popular class of "optimism in face uncertainty" methods. To do this, at the start of each episode, we define an upper bound on the possible average reward of each policy (Line 8): this average reward is computed as a combination of the average reward observed so far for this policy μ(π), the number of time steps this policy has been executed n(π) and H, which represents a guess of the span of the best policy, H + . We then select the policy with the maximum upper bound π (Line 9) to run for this episode. Unlike in multi-armed bandit settings where a selected arm is pulled for only one step, here the MDP policy is run for up to n(π) steps, i.e., until its total number of execution steps is at most doubled. If H ≥ H + then the confidence bounds computed (Line 8) are valid confidence intervals for the true best policy π + ; however, they may fail to hold for any other policy π whose span sp(λ π ) ≥ H. Therefore, we can cut off execution of an episode when these confidence bounds fail to hold (the condition specified on Line 12), since the policy may not be an optimal one for the current MDP, if H ≥ H + . 7 In this case, we can eliminate the current policy π from the set of policies considered in this trial (see Line 20). After an episode terminates, the parameters of the current policy π (the number of steps n(π) and average reward µ(π)) are updated, new upper bounds on the policies are computed, and the next episode proceeds. As the average reward estimates converge, the better policies will be chosen more.

Note that since we do not know H + in advance, we must estimate it online: otherwise, if H is not a valid upper bound for the span H + (see Assumption 1), a trial might eliminate the best policy π + , thus incurring a significant regret. We address this by successively doubling the amount of time T i each trial is run, and defining a H that is a function f of the current trial length. See Sec 4.1 for a more detailed discussion on the choice of f . This procedure guarantees the algorithm will eventually find an upper bound on the span H + and perform trials with very small regret in high probability. Finally, RLPA is an anytime algorithm since it does not need to know the time horizon T in advance.

Regret Analysis

In this section we derive a regret analysis of RLPA and we compare its performance to existing RL regret minimization algorithms. We first derive preliminary results used in the proofs of the two main theorems.

We begin by proving a general high-probability bound on the difference between average reward µ π and its empirical estimate µ(π) of a policy π (throughout this discussion we mean the average reward of a policy π on a new MDP M ). Let K(π) be the number of episodes π has been run, each of them of length v k (π) (k = 1, . . . , K(π)). The empirical average µ(π) is defined as

µ(π) = 1 n(π) K(π) k=1 v k (π) t=1 r k t , (4)
where

r k t ∼ r(•|s k t , π(s k t )
) is a random sample of the reward observed by taking the action suggested by π and n(π) = k v k (π) is the total count of samples. Notice that in each episode k, the first state s k 1 does not necessarily correspond to the next state of the last step v k-1 (π) of the previous episode.

Lemma 1. Assume that a policy π induces on the MDP M a single recurrent class with some additional transient states, i.e., µ π (s) = µ π for all s ∈ S. Then the difference between the average reward and its empirical estimate (Eq. 4) is

| µ(π) -µ π | ≤ 2(H π + 1) 2 log(2/δ) n(π) + H π K(π) n(π) , with probability ≥ 1 -δ, where H π = sp(λ π ) (see Eq. 2). Proof. Let rπ(s k t ) = E(r k t |s k t , π(s k t )), ǫr(t, k) = r k t -rπ(s k t )
, and P π be the statetransition kernel under policy π (i.e. for finite state and action spaces, P π is the |S|×|S| matrix where the ij-th entry is p(sj|si, π(si))). Then we have

µ(π) -µ π = 1 n(π) K(π) k=1 v k (π) t=1 (r k t -µ π ) = 1 n(π) K(π) k=1 v k (π) t=1 (ǫr(t, k) + rπ(s k t ) -µ π ) = 1 n(π) K(π) k=1 v k (π) t=1 (ǫr(t, k) + λ π (s k t ) -P π λ π (s k t )) ,
where the second line follows from Eq. 2. Let

ǫ λ (t, k) = λ π (s k t+1 ) -P π λ π (s k t ). Then we have µ(π) -µ π = 1 n(π) K(π) k=1 v k (π) t=1 (ǫr(t, k) + λ π (s k t+1 ) -λ π (s k t+1 ) + λ π (s k t ) -P π λ π (s k t )) ≤ 1 n(π) K(π) k=1 (H π + v k (π) t=1 ǫr(t, k) + v k (π)-1 t=1 ǫ λ (t, k)) ,
where we bounded the telescoping sequence t (λ π

s k t -λ π (s k t+1 )) ≤ sp(λ π ) = H π .
The sequences of random variables {ǫr} and {ǫ λ }, as well as their sums, are martingale difference sequences. Therefore we can apply Azuma's inequality and obtain the bound

µ(π) -µ π ≤ K(π)H π + 2 2n(π) log(1/δ) + 2H π 2(n(π) -K(π)) log(1/δ) n(π) ≤ H π K(π) n(π) + 2(H π + 1) 2 log(1/δ) n(π) ,
with probability ≥ 1δ, where in the first inequality we bounded the error terms ǫr, each of which is bounded in [-1, 1], and ǫ λ , bounded in [-H π , H π ]. The other side of the inequality follows exactly the same steps. ⊓ ⊔

In the algorithm H π is not known and at each trial i the confidence bounds are built using the guess on the span H = f (T i ), where f is an increasing function.

For the algorithm to perform well, it needs to not discard the best policy π + (Line 20). The following lemma guarantees that after a certain number of steps, with high probability the policy π + is not discarded in any trial.

Lemma 2. For any trial started after T ≥ T + = f -1 (H + ), the probability of policy π + to be excluded from Π A at anytime is less than (δ/T ) 6 .

Proof. Let i be the first trial such that Ti ≥ f -1 (H + ), which implies that H = f (Ti) ≥ H + . The corresponding step T is at most the sum of the length of all the trials before i, i.e., T ≤ i-1 j=1 2 j ≤ 2 i , thus leading to the condition T ≥ T + = f -1 (H + ). After T ≥ T + the conditions in Lem. 1 (with Assumption 1) are satisfied for π + . Therefore the confidence intervals hold with probability at least 1δ and we have for µ(π + )

µ(π + ) -µ + ≤ 2(H + + 1) 2 log(1/δ) n(π + ) + H + K(π + ) n(π + ) ≤ 2( H + 1) 2 log(1/δ) n(π + ) + H K(π + ) n(π + ) ,
where n(π + ) is number of steps when policy π + has been selected until T . Using a similar argument as in the proof of Lem. 1, we can derive

µ + - R(π + ) n(π + ) + v(π + ) ≤ 2( H + 1) 2 log(1/δ) n(π + ) + v(π + ) + H K(π + ) n(π + ) + v(π + )
, with probability at least 1-δ. Bringing together these two conditions, and applying the union bound, we have that the condition on Line12 holds with at least probability 1-2δ and thus π + is never discarded. More precisely Algo. 1 uses slightly larger confidence intervals (notably 48 log(2t/δ) instead of 2 2 log(1/δ)), which guarantees that π + is discarded with at most a probability of (δ/T ) 6 . ⊓ ⊔

We also need the B-values (line 9) to be valid upper confidence bounds on the average reward of the best policy µ + .

Lemma 3. For any trial started after T ≥ T + = f -1 (H + ), the B-value of π is an upper bound on µ + with probability ≥ 1 -(δ/T ) 6 .

Proof. Lem. 2 guarantees that the policy π + is in ΠA w.p. (δ/T ) 6 . This combined with Lem. 1 and the fact that f (T ) > H + implies that the B-value B(π

+ ) = µ(π + ) + c(π + )
is a high-probability upper bound on µ + and, since π is the policy with the maximum B-value, the result follows.

⊓ ⊔

Finally, we bound the total number of episodes a policy could be selected.

Lemma 4. After T ≥ T + = f -1 (H + ) steps of Algo. 1, let K(π) be the total number of episodes π has been selected and n(π) the corresponding total number of samples, then

K(π) ≤ log 2 (f -1 (H + )) + log 2 (T ) + log 2 (n(π)),
with probability ≥ 1 -(δ/T ) 6 .

Proof. Let n k (π) be the total number of samples at the beginning of episode k (i.e.,

n k (π) = k-1 k ′ =1 v k ′ (π)).
In each trial of Algo. 1, an episode is terminated when the number of samples is doubled (i.e., n k+1 (π) = 2n k (π)), or when the consistency condition (last condition on Line12) is violated and the policy is discarded or the trial is terminated (i.e., n k+1 ≥ n k (π)). We denote by K(π) the total number of episodes truncated before the number of samples is doubled, then n(π) ≥ 2 K(π)-K(π) . Since the episode is terminated before the number of samples is doubled only when either the trial terminates or the policy is discarded, in each trial this can only happen once per policy. Thus we can bound K(π) by the number of trials. A trial can either terminate because its maximum length Ti is reached or when all the polices are discarded (line 6). From Lem. 2, we have that after T ≥ f -1 (H + ), π + is never discarded w.h.p. and a trial only terminates when ti > Ti. Since Ti = 2 i , it follows that the number of trials is bounded by

K(π) ≤ log 2 (f -1 (H + )) + log 2 (T ). So, we have n(π) ≥ 2 K(π)-log 2 (f -1 (H + ))-log 2 (T )
, which implies the statement of the lemma.

⊓ ⊔

Notice that if we plug this result in the statement of Lem. 1, we have that the second term converges to zero faster than the first term which decreases as O(1/ n(π)), thus in principle it could be possible to use alternative episode stopping criteria, such as v(π) ≤ n(π). But while this would not significantly affect the convergence rate of µ(π), it may worsen the global regret performance in Thm. 1.

Gap-Independent Bound

We are now ready to derive the first regret bound for RLPA.

Theorem 1. Under Assumption 1 for any T ≥ T + = f -1 (H + ) the regret of Algo. 1 is bounded as

∆(s) ≤ 24(f (T ) + 1) 3T m(log(T /δ)) + √ T + 6f (T )m(log 2 (T + ) + 2 log 2 (T )),
with probability at least 1 -δ for any initial state s ∈ S.

Proof. We begin by bounding the regret from executing each policy π. We consider the k(π)-th episode when policy π has been selected (i.e., π is the optimistic policy π) and we study its corresponding total regret ∆π. We denote by n k (π) the number of steps of policy π at the beginning of episode k and v k (π) the number of steps in episode k. Also at time step T , let the total number of episodes, v k (π) and n k , for each policy π be denoted as K(π), v(π) and n(π) respectively. We also let π ∈ Π, B(π), c(π), R(π) and µ(π) be the latest values of these variables at time step T for each policy π. Let E = {∀t = f -1 (H + ), . . . , T, π + ∈ ΠA & π ≥ µ + } be the event under which π + is never removed from the set of policies ΠA, and where the upper bound of the optimistic policy π, B( π), is always as large as the true average reward of the best policy µ + . On the event E , ∆π can be bounded as

∆π = K(π) k=1 v k (π) t=1 (µ + -rt) (1)
≤

K(π) k=1 v k (π) t=1 (B(π) -rt) ≤ (n(π) + v(π))( µ(π) + c(π)) -R(π) (2)
≤ (n(π) + v(π)) 3(f (T ) + 1) 48 log(T /δ) n(π) + 3f (T ) K(π) n(π) (3)
≤ 24(f (T ) + 1) 3n(π) log(T /δ) + 6f (T )K(π),

where in (1) we rely on the fact that π is only executed when it is the optimistic policy, and B(π) is optimistic with respect to µ + according to Lem. 3. (2) immediately follows from the stopping condition at Line 12 and the definition of c(π).

(3) follows from the condition on doubling the samples (Line 12) which guarantees v(π) ≤ n(π).

We now bound the total regret ∆ by summing over all the policies.

∆ = π∈Π 24(f (T ) + 1) 3n(π) log(T /δ) + 6f (T ) π∈Π K(π) (1)
≤ 24(f (T ) + 1) 3m

π∈Π n(π) log(T /δ) + 6f (T ) π∈Π K(π) (2)
≤ 24(f (T ) + 1) 3mT log(T /δ) + 6f (T )m(log

2 (f -1 (H + )) + 2 log 2 (T )),
where in (1) we use Cauchy-Schwarz inequality and (2) follows from π n(π) ≤ T , Lem. 4, and log 2 (n(π)) ≤ log 2 (T ).

Since T is an unknown time horizon, we need to provide a bound which holds with high probability uniformly over all the possible values of T . Thus we need to deal with the case when E does not hold. Based on Lem. 1 and by following similar lines to [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], we can prove that the total regret of the episodes in which the true model is discarded is bounded by √ T with probability at least 1δ/(12T 5/4 ). Due to space limitations, we omit the details, but we can then prove the final result by combining the regret in both cases (when E holds or does not hold) and taking union bound on all possible values of T .

⊓ ⊔

A significant advantage of RLPA over generic RL algorithms (such as UCRL2) is that the regret of RLPA is independent of the size of the state and action spaces: in contrast, the regret of UCRL2 scales as O(S √ AT ). This advantage is obtained by exploiting the prior information that Π contains good policies, which allows the algorithm to focus on testing their performance to identify the best, instead of building an estimate of the current MDP over the whole stateaction space as in UCRL2. It is also informative to compare this result to other methods using some form of prior knowledge. In [START_REF] Maillard | Optimal regret bounds for selecting the state representation in re inforcement learning[END_REF] the objective is to learn the optimal policy along with a state representation which satisfies the Markov property. The algorithm receives as input a set of possible state representation models and under the assumption that one of them is Markovian, the algorithm is shown to have a sub-linear regret. Nonetheless, the algorithm inherits the regret of UCRL itself and still displays a O(S √ A) dependency on states and actions. In [START_REF] Dyagilev | Efficient reinforcement learning in parameterized models: Discrete parameter case[END_REF] the Parameter Elimination (PEL) algorithm is provided with a set of MDPs. The algorithm is analyzed in the PAC-MDP framework and under the assumption that the true model actually belongs to the set of MDPs, it is shown to have a performance which does not depend on the size of the stateaction space and it only has a O( √ m) a dependency on the number of MDPs m. 8 In our setting, although no model is provided and no assumption on the optimality of π * is made, RLPA achieves the same dependency on m. The span sp(λ π ) of a policy is known to be a critical parameter determining how well and fast the average reward of a policy can be estimated using samples (see e.g., [START_REF] Bartlett | Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps[END_REF]). In Thm. 1 we show that only the span H + of the best policy π + affects the performance of RLPA even when other policies have much larger spans. Although this result may seem surprising (the algorithm estimates the average reward for all the policies), it follows from the use of the third condition on Line12 where an episode is terminated, and a policy is discarded, whenever the empirical estimates are not consistent with the guessed confidence interval. Let us consider the case when H > H + but H < sp(λ π ) for a policy which is selected as the optimistic policy π. Since the confidence intervals built for π are not correct (see Lem. 1), π could be selected for a long while before selecting a different policy. On the other hand, the condition on the consistency of the observed rewards would discard π (with high probability), thus increasing the chances of the best policy (whose confidence intervals are correct) to be selected. We also note that H + appears as a constant in the regret through log 2 (f -1 (H + )) and this suggests that the optimal choice of f is f (T ) = log(T ), which would lead to a bound of order (up to constants and logarithmic terms) O( √ T m + m).

Gap-Dependent Bound

Similar to [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], we can derive an alternative bound for RLPA where the dependency on T becomes logarithmic and the gap between the average of the best and second best policies appears. We first need to introduce two assumptions.

Assumption 2 (Average Reward) Each policy π ∈ Π induces on the MDP M a single recurrent class with some additional transient states, i.e., µ π (s) = µ π for all s ∈ S. This implies that H π = sp(λ π ) < +∞.

Assumption 3 (Minimum Gap) Define the gap between the average reward of the best policy π + and the average reward of any other policy as Γ (π, s) = µ + -µ π (s) for all s ∈ S. We then assume that for all π ∈ Π -{π + } and s ∈ S, Γ (π, s) is uniformly bounded from below by a positive constant Γ min > 0.

Theorem 2 (Gap Dependent Bounds). Let Assumptions 2 and 3 hold. Run Algo. 1 with the choice of δ = 3 1/T (the stopping time T is assumed to be known here). Assume that for all π ∈ Π we have that H π ≤ H max . Then the expected regret of Algo. 1, after T ≥ T + = f -1 (H + ) steps, is bounded as

E(∆(s)) = O m (f (T ) + H max )(log 2 (mT ) + log 2 (T + )) Γ min , (5)
for any initial state s ∈ S.

Proof. (sketch) Unlike for the proof of Thm. 1, here we need a more refined control on the number of steps of each policy as a function of the gaps Γ (π, s). We first notice that Assumption 2 allows us to define Γ (π) = Γ (π, s) = µ +µ π for any state s ∈ S and any policy π ∈ Π. We consider the high-probability event E = {∀t = f -1 (H + ), . . . , T, π + ∈ ΠA} (see Lem. 2) where for all the trials run after f -1 (H + ) steps never discard policy π + . We focus on the episode at time t, when an optimistic policy π = π + is selected for the k(π)-th time, and we denote by n k ( π) the number of steps of π before episode k and v k (π) the number of steps during episode k(π).

The cumulative reward during episode k is R k ( π) obtained as the sum of µ k ( π)n k ( π) (the previous cumulative reward) and the sum of v k ( π) rewards received since the beginning of the episode. Let E = {∀t = f -1 (H + ), . . . , T, π + ∈ ΠA & π ≥ µ + } be the event under which π + is never removed from the set of policies ΠA, and where the upper bound of the optimistic policy µ, B( π), is always as large as the true average reward of the best policy µ + . On event E we have

3( H + 1) 48 log(t/δ) n k ( π) + 3 k(π) n k ( π) (1) ≥ B( π) - R k ( π) n k ( π) + v k ( π) (2) ≥ µ + - R k ( π) n k ( π) + v k ( π) ≥ µ + -µ π + 1 n k ( π) + v k ( π) n k ( π)+v k ( π) t=1 (µ π -rt) (3) ≥ Γmin + 1 n k ( π) + v k ( π) n k ( π)+v k ( π) t=1 (µ π -rt) (4) ≥ Γmin -H π 48 log(t/δ) n k ( π) -H π K( π) n k ( π) ,
with probability 1 -(δ/t) 6 . Inequality ( 1) is enforced by the episode stopping condition on Line12 and the definition of B(π), (2) is guaranteed by Lem. 3, (3) relies on the definition of gap and Assumption 3, while ( 4) is a direct application of Lem. 1.

Rearranging the terms, and applying Lem. 4, we obtain

n k ( π)Γmin ≤ (3 H + 3 + H π ) n( π) 48 log(t/δ) + 4H π (2 log 2 (t) + log 2 (f -1 (H + ))).
By solving the inequality w.r.t. n k ( π) we obtain

n( π) ≤ (3 H + 3 + H π ) 48 log(t/δ) + 2 H π Γmin(2 log 2 (t) + log 2 (f -1 (H + )) Γmin , (6)
w.p. 1 -(δ/t) 6 . This implies that on the event E , after t steps, RLPA acted according to a suboptimal policy π for no more than O(log(t)/Γ 2 min ) steps. The rest of the proof follows similar steps as in Thm. 1 to bound the regret of all the suboptimal policies in high probability. The expected regret of π + is bounded by H + and standard arguments similar to [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] are used to move from high-probability to expectation bounds.

⊓ ⊔

Note that although the bound in Thm. 1 is stated in high-probability, it is easy to turn it into a bound in expectation with almost identical dependencies on the main characteristics of the problem and compare it to the bound of Thm. 2. The major difference is that the bound in Eq. 5 shows a O(log(T )/Γ min ) dependency on T instead of O( √ T ). This suggests that whenever there is a big margin between the best policy and the other policies in Π, the algorithm is able to accordingly reduce the number of times suboptimal policies are selected, thus achieving a better dependency on T . On the other hand, the bound also shows that whenever the policies in Π are very similar, it might take a long time to the algorithm before finding the best policy, although the regret cannot be larger than O( √ T ) as shown in Thm. 1. We also note that while Assumption 3 is needed to allow the algorithm to "discard" suboptimal policies with only a logarithmic number of steps, Assumption 2 is more technical and can be relaxed. It is possible to instead only require that each policy π ∈ Π has a bounded span, H π < ∞, which is a milder condition than requiring a constant average reward over states (i.e., µ π (s) = µ π ).

Computational Complexity

As shown in Algo. 1, RLPA runs over multiple trials and episodes where policies are selected and run. The largest computational cost in RLPA is at the start of each episode computing the B-values for all the policies currently active in Π A and then selecting the most optimistic one. This is an O(m) operation. The total number of episodes can be upper bounded by 2 log 2 (T ) + log 2 (f -1 (H + )) (see Lem. 4). This means the overall computational of RLPA is of O(m(log 2 (T ) + log 2 (f -1 (H + )))). Note there is no explicit dependence on the size of the state and action space. In contrast, UCRL2 has a similar number of trials, but requires solving extended value iteration to compute the optimistic MDP policy. Extended value iteration requires O(|S| 2 |A| log(|S|)) computation per iteration: if D are the number of iterations required to complete extended value iteration, then the resulting cost would be O(D|S| 2 |A| log(|S|). Therefore UCRL2, like many generic RL approaches, will suffer a computational complexity that scales quadratically with the number of states, in contrast to RLPA, which depends linearly on the number of input policies and is independent of the size of the state and action space.

Experiments

In this section we provide some preliminary empirical evidence of the benefit of our proposed approach. We compare our approach with two other baselines. As mentioned previously, UCRL2 [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] is a well known algorithm for generic RL problems that enjoys strong theoretical guarantees in terms of high probability regret bounds with the optimal rate of O( √ T ). Unlike our approach, UCRL2 does not make use of any policy advice, and its regret scales with the number of states and actions as O(|S| |A|). To provide a more fair comparison, we also introduce a natural variant of UCRL2, Upper Confidence with Models (UCWM), which takes as input a set of MDP models M which is assumed to contain the actual model M . Like UCRL2, UCWM computes confidence intervals over the task's model parameters, but then selects the optimistic policy among the optimal policies for the subset of models in M consistent with the confidence interval. This may result in significantly tighter upper-bound on the optimal value function compared to UCRL2, and may also accelerate the learning process. If the size of possible models shrinks to one, then UCWM will seamlessly transition to following the optimal policy for the identified model. UCWM requires as input a set of MDP models, whereas our RLPA approach requires only input policies.

We consider a square grid world with 4 actions: up (a 1 ), down (a 2 ), right (a 3 ) and left (a 4 ) for every state. A good action succeeds with the probability 0.85, and goes in one of the other directions with probability 0.05 (unless that would cause it to go into a wall) and a bad action stays in the same place with probability 0.85 and goes in one of the 4 other directions with probability 0.0375. We construct four variants of this grid world M = {M 1 , M 2 , M 3 , M 4 }. In model 1 (M 1 ) good actions are 1 and 4, in model 2 (M 2 ) good actions are 1 and 2, in model 3 good actions are 2 and 3, and in model 4 good actions are 3 and 4. All other actions in each MDP are bad actions. The reward in all MDPs is the same and is -1 for all states except for the four corners which are: 0.7 (upper left), 0.8 (upper right), 0.9 (lower left) and 0.99 (lower right). UCWM receives as input the MDP models and RLPA receives as input the optimal policies of M.

We evaluate the performances of each algorithm in terms of the per-step regret, ∆ = ∆/T (see Eq. 3). Each run is T = 100000 steps and we average the performance on 100 runs. The agent is randomly placed at one of the states of the grid at the beginning of each round. We assume that the true MDP model is M 4 . Notice that in this case π * ∈ Π, thus µ + = µ * and the regret compares to the optimal average reward. The identity of the true MDP is not known by the agent. For RLPA we set f (t) = log(t). 9 We construct grid worlds of various sizes and compare the resulting performance of the three algorithms.

Fig. 1 shows per-step regret of the algorithms as the function of the number of states. As predicted by the theoretical bounds, the per-step regret ∆ of UCRL2 significantly increases as the number of states increases, whereas the average regret of our RLPA is essentially independent of the state space size 10 . Although UCWM has a lower regret than RLPA for a small number of states, it quickly loses its advantage as the number of states grows. UCRL2's per-step regret plateaus after a small number of states since it is effectively reaching the maximum possible regret given the available time horizon.

To demonstrate the performance of each approach for a single task, Fig. 2(a) shows how the per-step regret changes with different time horizons for a gridworld with 64 states. RLPA demonstrates a superior regret throughout the run with a decrease that is faster than both UCRL and UCWM. The slight periodic increases in regret of RLPA are when a new trial is started, and all policies are again considered. We also note that the slow rate of decrease for all three algorithms is due to confidence intervals dimensioned according to the theoretical results which are often over-conservative, since they are designed to hold in the worst-case scenarios. Finally, Fig. 2(b) shows the average running time of one trial of the algorithm as a function of the number of states. As expected, RLPA's running time is independent of the size of the state space, whereas the running time of the other algorithms increases.

Though a simple domain, these empirical results support our earlier analysis, demonstrating RLPA exhibits a regret and computational performance that is essentially independent of the size of the domain state space. This is a significant advantage over UCRL2, as we might expect because RLPA can efficiently leverage input policy advice. Interestingly, we obtain a significant improvement also over the more competitive baseline UCWM.

Related Work

The setting we consider relates to the multi-armed bandit literature, where an agent seeks to optimize its reward by uncovering the arm with the best expected reward. More specifically, our setting relates to restless [START_REF] Ortner | Regret bounds for restless markov bandits[END_REF] and rested [START_REF] Tekin | Online learning of rested and restless bandits[END_REF] bandits, where each arm's distribution is generated by a an (unknown) Markov chain that either transitions at every step, or only when the arm is pulled, respectively. Unlike either restless or rested bandits, in our case each "arm" is itself a MDP policy, where different actions may be chosen. However, the most significant distinction may be that in our setting there is a independent state that couples the rewards obtained across the policies (the selected action depends on both the policy/arm selected, and the state), in contrast to the rested and restless bandits where the Markov chains of each arm evolve independently.

Prior research has demonstrated a significant improvement in learning in a discrete state and action RL task whose Markov decision process model parameters are constrained to lie in a finite set. In this case, an objective of maximizing the expected sum of rewards can be framed as planning in a finite-state partially observable Markov decision process [START_REF] Poupart | An analytic solution to discrete bayesian reinforcement learning[END_REF]: if the parameter set is not too large, off-the-shelf POMDP planners can be used to yield significant performance improvements over state-of-the-art RL approaches [START_REF] Brunskill | Bayes-optimal reinforcement learning for discrete uncertainty domains[END_REF]. Other work [START_REF] Dyagilev | Efficient reinforcement learning in parameterized models: Discrete parameter case[END_REF] on this setting has proved that the sample complexity of learning to act well scales independently of the size of the state and action space, and linearly with the size of the parameter set. These approaches focus on leveraging information about the model space in the context of Bayesian RL or PAC-style RL, in contrast to our model-free approach that focuses on regret.

There also exists a wealth of literature on learning with expert advice (e.g. [START_REF] Cesa-Bianchi | How to use expert advice[END_REF]). The majority of this work lies in supervised learning. Prior work by Diuk et al. [START_REF] Diuk | The adaptive k-meteorologists problem and its application to structure learning and feature selection in reinforcement learning[END_REF] leverages a set of experts where each expert predicts a probabilistic concept (such as a state transition) to provide particularly efficient KWIK RL. In contrast, our approach leverages input policies, rather than models. Probabilistic policy reuse [START_REF] Fernández | Probabilistic policy reuse in a reinforcement learning agent[END_REF] also adaptively selects among a prior set of provided policies, but may also choose to create and follow a new policy. The authors present promis-ing empirical results but no theoretical guarantees are provided. However, we will further discuss this interesting issue more in the future work section.

The most closely related work is by Talvitie and Singh [START_REF] Talvitie | An experts algorithm for transfer learning[END_REF], who also consider identifying the best policy from a set of input provided policies. Talvitie and Singh's approach is a special case of a more general framework for leveraging experts in sequential decision making environments where the outcomes can depend on the full history of states and actions [START_REF] Pucci De Farias | Exploration-exploitation tradeoffs for experts algorithms in reactive environments[END_REF]: however, this more general setting provides bounds in terms of an abstract quantity, whereas Talvitie and Singh provide bounds in terms of the bounds on mixing times of a MDP. There are several similarities between our algorithm and the work of Talvitie and Singh, though in contrast to their approach we take an optimism under uncertainty approach, leveraging confidence bounds over the potential average reward of each policy in the current task. However, the provided bound in their paper is not a regret bound and no precise expression on the bound is stated, rendering it infeasible to do a careful comparison of the theoretical bounds. In contrast, we provide a much more rigorous theoretical analysis, and do so for a more general setting (for example, our results do not require the MDP to be ergodic). Their algorithm also involves several parameters whose values must be correctly set for the bounds to hold, but precise expressions for these parameters were not provided, making it hard to perform an empirical comparison.

Future Work and Conclusion

In defining RLPA we preferred to provide a simple algorithm which allowed us to provide a rigorous theoretical analysis. Nonetheless, we expect the current version of the algorithm can be easily improved over multiple dimensions. The immediate possibility is to perform off-policy learning across the policies: whenever a reward information is received for a particular state and action, this could be used to update the average reward estimate µ(π) for all policies that would have suggested the same action for the given state. As it has been shown in other scenarios, we expect this could improve the empirical performance of RLPA. However, the implications for the theoretical results are less clear. Indeed, updating the estimate µ(π) of a policy π whenever a "compatible" reward is observed would correspond to a significant increase in the number of episodes K(π) (see Eq. 4). As a result, the convergence rate of µ(π) might get worse and could potentially degrade up to the point when µ(π) does not even converge to the actual average reward µ π . (see Lem. 1 when K(π) ≃ n(π)). We intend to further investigate this in the future.

Another very interesting direction of future work is to extend RLPA to leverage policy advice when useful, but still maintain generic RL guarantees if the input policy space is a poor fit to the current problem. More concretely, currently if π + is not the actual optimal policy of the MDP, RLPA suffers an additional linear regret to the optimal policy of order T (µ * -µ + ). If T is very large and π + is highly suboptimal, the total regret of RLPA may be worse than UCRL, which always eventually learns the optimal policy. This opens the question whether it is possible to design an algorithm able to take advantage of the small regret-tobest of RLPA when T is small and π + is nearly optimal and the guarantees of UCRL for the regret-to-optimal.

To conclude, we have presented RLPA, a new RL algorithm that leverages an input set of policies. We prove the regret of RLPA relative to the best policy scales sub-linearly with the time horizon, and that both this regret and the computational complexity of RLPA are independent of the size of the state and action space. This suggests that RLPA may offer significant advantages in large domains where some prior good policies are available.

Fig. 1 .

 1 Fig. 1. Per-step regret versus number of states.

  Avg. per-step regret vs time step.

  Running time versus |S|.

The extension to larger bounded regions [0, d] is trivial and just introduces an additional d multiplier to the resulting regret bounds.

One can easily prove that the upper bound H always exists for any unichain Markov reward process (see[START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] Chap. 8]).

Note that Assumption 1 in general is a weaker assumption than assuming MDP M is ergodic or unichain, which would require that the induced Markov chains under all policies be recurrent or unichain, respectively: we only require that the best policy in the input set must induce a unichain Markov process.

See Sec. 4.1 for further discussion on the necessity of the condition on Line 12.

Notice that PAC bounds are always squared w.r.t. regret bounds, thus the original m dependency in[START_REF] Dyagilev | Efficient reinforcement learning in parameterized models: Discrete parameter case[END_REF] becomes O( √ m) when compared to a regret bound.

See Sec. 4.1 for the rational behind this choice.

The RLPA regret bounds depend on the bias of the optimal policy which may be indirectly a function of the structure and size of the domain.


Jimenez Carrizosa

Abdelkrim Benchaib
email: abdelkrim.benchaib@alstom.com

Pedro Alou
email: pedro.alou@upm.es

Gilney Damm
email: gilney.damm@ibisc.fr

M Jiménez Carrizosa

DC transformer for DC/DC connection in HVDC network

Keywords: <<DAB>>, <<multilevel>>, <<nonlinear control>>, <<HVDC>>, <<Plug & Play>>

teaching and research institutions in France or abroad, or from public or private research centers.

DC transformer for DC/DC connection in HVDC network

Introduction

World energy demand is progressively growing while fossil fuels deplete. Moreover, renewable energy sources are often located far away from consumption centers (e.g. offshore wind farms). For this reason, power delivery through long distances is getting increasingly important. From the beginning of 20 th century and up to nowadays, electric power has been predominantly transmitted and distributed in AC due to the unavailability of well-suited DC/DC converters. However, the emergence of a wider range of power electronics devices is contributing to revitalize the research on DC transmission networks. DC grids present several advantages in comparison with AC grids: in DC networks there are not reactive power, so their transmission capacities are increased, they also produce fewer losses than AC grids, the weight and cost of components is lower (fewer cables), and the efficiency is higher [START_REF] Arrillaga | Flexible Power Transmission. The HVDC Options[END_REF][START_REF] Asplund | Ultra high voltaje trasmission[END_REF][START_REF] Kreuse | The future is now[END_REF][START_REF] Ravemark | Light and invisible[END_REF]. It is in this context where DC/DC converters play a decisive role. Since energy is generated at low voltages and highly efficient devices are needed to increase these voltages to higher values. Furthermore, these converters have to be bidirectional. This paper discusses the topology and the control of a DC/DC bidirectional converter valid for the integration of an offshore wind farm in a High Voltage Direct Current (HVDC). Until developed of VSC (voltage source converters), in HVDC systems were used the CSC (current source converters) to carry out the inversion and rectification. VSC converters use IGBTs and CSC use thyristors. VSC-HVDC systems present many advantages compared with CSC-HVDC systems. Some of them are: simultaneous control of active and reactive power, they create any phase angle or voltage magnitude (within certains limits),and they do not change voltage polarity when power direction is changed. Also CSC systems need communication between converters and in VSC systems it is not required [START_REF] Johansson | Power system stability. benefits with vschvdc transmission systems[END_REF]. We will suppose in this paper that we will employ VSC-systems, but the goal of this paper is to developed the DC/DC converter. The proposed converter would be located according to Figure 1.

The paper is outlined as follows: Section I presents the introduction and the background information on the study. Section II presents an overview of existing high-power DC/DC converter topologies. Then the most suitable converter cell (DAB type) is chosen as a base-cell for the multilevel converter. Section III presents the modeling and control of a single DAB converter cell. The proposed control is a robust nonlinear control based on Lyapunov theory. Section IV presents the modeling and the control of the whole multilevel structure. In Section V the conclusions are explained.

DC/DC Bi-Directional Converters. State of the Art

As found in the literature, this report will show 3 main topologies which should be good candidates for our purpose. They are: DAB, SRC (Series Resonant Converter) and DHB (Dual Half Bridge). Such converter with its associated control algorithm will be considered as the basic block of a multilevel converter for HVDC applications. Our aim is to obtain a building block DC converter based on the so-called "Plug & play" philosophy.

Dual Active Bridge (DAB)

The dual active bridge, DAB, is comprised of two full bridge converters each connected to one side of the transformer, which will provide galvanic insulation (necessary to protect against unforeseen circumstances) [START_REF] Ortiz | 1 mw, 20 khz, isolated, 1.2-12kv bidirectional dc-dc renawable converter for energy applications[END_REF]. DAB control will take place with rectangular modulation. This topology can enable a ZCS (zero current switching) in the high voltage side of the converter. An inductance L, which is used as a component of energy transfer, is placed in series with the transformer. The scheme of this structure is shown in Figure 2a. Medium frequency transformer is used [START_REF] Ortiz | Optimized design of medium frequency transformers with high isolation requirements[END_REF][START_REF] Aggeler | Solid-state transformer based on sic jfet for future energy distribution systems[END_REF] . It provides insulation and the step up/down of the different voltage levels. This transformer is based on a single magnetic core with windings in both legs of the core. Using this type of transformer the ratio weight/volume could be improved. It works at frequencies around 10/20 kHz [START_REF] Ortiz | Optimized design of medium frequency transformers with high isolation requirements[END_REF]. For this type of converter SiC-JFETs can be used [START_REF] Biela | 5kv/200ns pulsed power switch based on a sic-jfet super cascode[END_REF][START_REF] Friedrichs | Stacked high voltage switch based on sic vjfets[END_REF][START_REF] Singhi | Ultra high voltage sic bipolar devices for reduced power electronics complexity[END_REF][START_REF] Palmour | High voltage silicon carbide power devices[END_REF], but the object of this paper is not study in depth the semiconductors and the internal transformers.

Series Resonant Converter (SRC)

This converter consists of two full bridges interfaced by a transformer with a series resonant tank composed of an inductor L and a capacitor C. The SRC converter represents an attractive alternative for the HV-ZCS current modulation [START_REF] Ortiz | 1 mw, 20 khz, isolated, 1.2-12kv bidirectional dc-dc renawable converter for energy applications[END_REF]. Piecewise sinusoidal current waveforms are obtained through the transformer with this resonant tank. The scheme structure is shown in Figure 2b:

Dual Half Bridge (DHB)

Dual half bridge (DHB) is a popular topology among phase-shift ZVS bidirectional DC-DC converters [START_REF] Fan | High frequency high efficiency bidirectional dc-dc converter module design for 10 kva solid state transformer[END_REF]. To achieve ZVS a is adopted for all switching devices without auxiliary switch devices in either direction of power flow, and therefore it enables the high switching frequency operation with low switching losses. The scheme structure is shown in Figure 2c.

Multilevel converter

One of the most important parts of power electronics converters are the semiconductor, because they must withstand high currents when they are "on" and large voltages when they are "off". If a large input/output voltage ratio is required, a single converter would not be enough, and an attractive solution is the interconnection of several converters modules or cells in series and parallel. This arrangement is commonly known as a multilevel converter. The multilevel solution adopted in this paper is illustrated in Figure 3. These types of converters are connected in multilevel structure for high power application, where each module is a bidirectional DC-DC converter constituting a bidirectional multilevel structure. This Multilevel structure consists of multiple low-voltage modules connected in series in one side and parallel in the other side.

Discussions and topology selection

Three main topologies have been reviewed in this paper which all of them have advantages and drawbacks (see Table I). We will choose just one topology in order to perform DC/DC conversion and to test our future algorithms on DC grid. All of these topologies have been extensively tested and their performances experienced, so these topologies could be good candidates.

Since it uses fewer semiconductors, the DHB topology seems to be the most cost effective compared to DAB and SRC. However, the DHB topology have two main drawbacks: it is limited in power and high currents appear though the transformer and semiconductors in comparison with others. Moreover, the full-bridge topologies (DAB and SRC) allow applying zero volts to the transformer, so they have more degrees of freedom than the DHB topology. In this way, the voltage sources would provide less reactive power in the case of full bridge than the case of DHB topology. The main difference between the DAB topology and the SRC is that, in the SRC there is a capacitor in series with the inductance which does not exist in DAB configuration. The role of this capacitor is to resonate with the series inductance, reaching a sinusoidal current. Variable frequency is required in the SRC to obtain optimum performance. Consequently and thanks to its simplicity and cost efficiency compared to SRC, the DAB converter has been chosen to perform DC-DC conversion as single transformer module and in multilevel configuration for DC grid applications.

As shown in Figure 2a, the DAB system which is based on power electronics is inherently discontinuous and consequently not adapted for control algorithm synthesis. In this work a continuous model is proposed. In order to simplify our circuit modeling, we will assume that the conduction losses are taken into account via small resistance R total . In the modeling process, we will assume that the capacitors C 1 and C 2 are always precharged at the voltage levels V in and V out . Therefore, these capacitors can be considered as ideal voltage sources with internal resistances (including in R total ). If all the parameters are seen from the primary side, we obtain the following simplified scheme as shown in Figure 4. To avoid short circuits and possible saturation of the transformer and the inductance, a zero average value of voltage is applied in each cycle. Consequently, a zero current average value is obtained in steady state. To achieve this claim, there exist several possibilities in the sequence of switching the power electronic components. Two interesting strategies have been shown in [START_REF] Ortiz | 1 mw, 20 khz, isolated, 1.2-12kv bidirectional dc-dc renawable converter for energy applications[END_REF][START_REF] Sebastián | An overall study of a dual active bridge for bidirectional dc/dc conversion[END_REF], where the authors have shown the advantages and drawbacks of each technique. In this proposed work, it is chosen to work with the method proposed in [START_REF] Sebastián | An overall study of a dual active bridge for bidirectional dc/dc conversion[END_REF] (rectangular modulation), which ultimately is to play with the variable d representing the phase shift ratio between the voltages applied to the inductance V a and V b . In order to have a bidirectional converter, the phase shift ratio d is defined in the interval 0 < d < 0.5 for power flowing from left side to right side, and in the interval -0.5 < d < 0 for power flowing in the opposite direction. The applied voltages V a and V b , the current i L , the voltage V L in the inductance and currents i 1 and i 2 with their average values < i 1 > and < i 2 > (discontinuous lines) are obtained for a few cycles in (steady state) in Figure 5. It shows two interesting things. At first, and for the chosen phase shift ratio (0 < d < 0.5), the average values of currents (< i 1 > and < i 2 >) are positive. This means that the power is flowing from the source V in to V out . Secondly, we can remark that the average values of voltage and current applied to the inductance are zero. For all cases study , the following equations hold:

a = T 4L [V in + (4|d| -1) V out n ] b = T 4L [(4|d| -1) •V in + V out n ] ⇒ < i 1 >= T L • d • (1 -2|d|) V out n < i 2 >= T n•L • d • (1 -2|d|)V in (1)

Dynamics of the real system

In order to design the nonlinear control based in Lyapunov theory a differential equation that adjusts to the real system is required. The control is performed on the mean value of current i 1 , so all calculations based on this will be indicated with respect to the current i 1 . The differential equation which governs the system is:

d dt < i 1 > (t) = - R total L • < i 1 > (t) + T • R total L 2 • d • (1 -2|d|) V out n (2)
Now, we are going to proof this equation 2 in the case of 0 < d < 0.5. The case of negative d is analogous.We have assumed that V in < V out n , but if we chose the opposite, we can reach the same result.

In [0, d • T ] we have (U = V in + V out n ): d dt i L (t) = - R L • i L (t) + U L ⇒ b 0 = i L (d • t) = a 0 • e -R L d•t + 1 -e -R L d•t V in + V out n R (3)
Now for [d • T, T /2] we proceed the same way as above, but now U = V in -V out n . So:

a 1 = i L ( T 2 ) = b 0 • e -R L ( 1 2 -d)T + 1 -e -R L ( 1 2 -d)T V in -V out n R (4)
Now is possible to put a 1 in terms of a 0 , because b 0 depends on a 0 , the expression is:

a 1 = a 0 • e -RT 2L + 1 -e -RT 2L V in R -1 -2e -R L ( 1 2 -d)T +e -RT 2L V out n • R (5)
As in the second part of the period the differential equations that govern the system are equal but with opposite voltages applied, proceeding in a similar way we obtain a 2 in terms of a 1 :

a 2 = a 1 • e -RT 2L -1 -e -RT 2L V in R + 1 -2e -R L ( 1 2 -d)T +e -RT 2L V out n • R (6)
Replacing equation 5 into 6, and put it in general terms we have:

a n+2 + (1 -e -RT 2L )a n+1 -(e -RT 2L )a n = 0 (7)
That is a homogeneous linear recurrent succession with constant coefficients whose characteristic polynomial is:

a n = Cte 1 • (-1) n +Cte 2 • e -n RT 2L ⇒    Cte 1 = a 0 •e -RT 2L -a 1 1+e -RT 2L Cte 2 = a 0 +a 1 1+e -RT 2L ( 8
)
The limit of the sub-succession of even terms and odd are shown in equations 9 and 10 respectively:

lim n→+∞ a 2n = Cte 1 = -1 -e -RT 2L V in R + 1 -2e -R L ( 1 2 -d)T + e -RT 2L V out n•R 1 + e -RT 2L (9) lim n→+∞ a 2n+1 = -Cte 1 = 1 -e -RT 2L V in R -1 -2e -R L ( 1 2 -d)T + e -RT 2L V out n•R 1 + e -RT 2L (10)
It should be pointed out that the two expressions given above are independent of the initial values. Note that in steady a 2n and a 2n+2 terms have the same value, and a 2n+1 has the same value as a 2n and a 2n+2 but with opposite sign. The mean value of the current i 1 in the interval [n • T, (n + 1) • T ] is:

< i 1 >= c • a 2n + k(d) ⇒ c = L RT • 1 -e -RT 2L k(d) = 1 -3L RT 1 -e -RT 2L • V in R + 4d -1 + 3L RT 1 -2 • e -R L •( 1 2 -d)T • Vout n•R (11)
If the periodic stepwise input signal does not change (voltage of sources), the dynamic of the succession of the values of < i 1 > in each period is the same as the succession of their initial values (a 2n ), so both have the same time constant τ. For a first order system, it is by definition the time that the increase of the input signal reaches the value 1 -1 e times the final increase value, when the input is constant. So:

(final value-a 0 ) 1 -1 e = a 2n -a 0 (12)
The final value is obtained by the following expression: [START_REF] Fan | High frequency high efficiency bidirectional dc-dc converter module design for 10 kva solid state transformer[END_REF] We can obtain that n • T = L R , where n is the number of periods for which the time constant reaches τ = n • T . Once we know the time constant, both for the succession of initial values and for the succession of average current values, is τ = L R , as the system for the current is a linear differential system of first order whose general expression is:

lim n→+∞ a 2n = a 0 • e -RT 2L -a 1 1 + e -RT 2L
d dt < i 1 > (t) = - < i 1 > (t) τ +Cte (14)
Cte is a constant must be calculated. In equation 1, the average current in the steady state was calculated. Applying this result to equation 14 in steady state, one has:

Cte = T τ • L • d • (1 -2|d|) V out n = T R L 2 • d • (1 -2|d|) V out n (15)
So, we have demostrated that equation 14 has the same behaviour that equation 2 as we want to demonstrated ✷. In Figure 6 the solid plot corresponds to the real value of i 1 and the dashed plot is the output of our model corresponding to the differential equation 2. Figure 6 shows that the dynamic of the peaks of solid plot is the same as the dynamic of the dashed plot, so the transient behavior of the real current i 1 is the same that in the differential equation. In steady state the value of the average current i 1 is given by equation 1 which is the same as the steady state value in the differential equation 2, so that it can be concluded that our model of equation differential is correctly modeled.

Verification of differential equation

Nonlinear control design for DAB system

The proposed control law will be based on Lyapunov theory, see [START_REF] Isidori | Nonlinear control systems[END_REF][START_REF] Khalil | Nonlinear systems[END_REF]. Consider the dynamic model represented in equation 2 Our aim is to track the reference of the average current < i 1 > re f . Consider the following Lyapunov energy representing the needed energy necessary for the current to converge to its reference.

Q <i 1 > = 1 2 (< i 1 > -< i 1 > re f ) 2 (16)
Its derivate time is:

d dt Q <i 1 > = E <i1> • -R L < i 1 > (t) + T R L 2 • d • (1 -2|d|) V out n -d dt < i 1 > re f ( 17
)
where the

E <i1> = (< i 1 > -< i 1 > re f
) is the tracking error. In order to achieve to desired tracking as well as control stability, it is sufficient to force negative the derivative time of the Lyapunov function. In order to achieve negative derivate of the Lyapunov function:

-R L < i 1 > (t) + T R L 2 • d • (1 -2|d|) V out n -d dt < i 1 > re f = -α <i1> • E <i1> -β <i1> • sign(E <i1> ) (18)
with the positive tuning gain parameters α <i1> > 0, β <i1> > 0. As it is well known in the sliding mode control theory, the sign function is added to improve the robustness properties of the proposed control law. Thereafter, the time derivative of the Lyapunov function becomes:

d dt Q <i 1 > = -α <i1> • E 2 <i1> -β <i1> • sign(E <i1> ) • E <i1> ≤ 0 ( 19
)
Equation 19 is satisfying the stability condition. So, the following relation holds from equation 18:

d(1 -2|d|) = n•L 2 R•T •V out -α <i1> E <i1> -β <i1> sign(E <i1> ) + d dt < i 1 > re f + R L < i 1 > (20)
Let consider the right hand side of equation 20 as:

K = n • L 2 RTV out -α <i1> E <i1> -β <i1> sign(E <i1> ) + d dt < i 1 > re f + R L < i 1 > (21)
Developing equation 20, we obtain the general solution for the two cases leads to the control law which able to track the reference and to ensure the system stability:

d(1 -2|d|) = d -2d 2 , f or d ≥ 0 d + 2d 2 , f or d ≤ 0 ⇒ d = 1 - √ 1 -8K 4 • S 1 + -1 + √ 1 + 8K 4 • S 2 (22)
where S 1 has value 1 if the condition K > 0 is true and 0 otherwise. The same applies for S 2 with the condition K < 0.

Real situation

The goal of the converter is to be bidirectional, that is, it must be capable of changing the direction of the power at every instant. To do this, it is enough to change the reference current. The control is verified simulating a real situation where the current reference varies in the time. It should be noted that depending on the reference current imposed the power transmitted will be higher or lower. Figure 7a shows that the system behaves well with respect to the different changes in the reference signal and Figure 7b shows that d behaves correctly. As shown in section 2.4, the proposed multilevel structure seems to be a good alternative for voltage elevation and multi-terminal DC grid interconnection. Once a robust control algorithm has been developed for DAB converter, our aim is to propose a multilevel "Plug & Play" structure with DAB module association capable to raise the voltage output. It should be pointed out that the DAB module considered here is made of the DAB converter with its control system as shown in Figure 3.

The local controllers are designed as shown in section 3.3 and given by equation 22. There is not need for additional control design and tuning parameters. The global controller (called also master controller) sends the requested references to each module in order to fulfill the global control requirements. If a failure occurs in a given module, the global controller will send an order to bypass the deteriorated module and keep the multilevel working in the voltage margin assigned by the operator. The deteriorated module can be replaced later with the global control acting in the same "Plug & Play" philosophy. Once the regulation for a single module is obtained, the next step is to connect the modules as mentioned in section 2.4. This association of modules will help to obtain higher voltage ratios, without semiconductors suffering from it. Each module is controlled by the regulation obtained in the previous chapter. If 3 MW want to be transmitted, emulating a wind turbine providing power to the network, with a ratio of 1 kV/150 kV, fifteen modules (with ratio 1kV/10kV) are connected, as it shows in Figure 8. In this case the current reference in the primary of each module are 200 A, so that the total current is 3000 A, and with this current the desired power (3 MW) is obtained. The Figure 9a shows the current through the left side in each module. As shown in Figure 9a, in the primary of each module there are 200 A, as expected. This means that our regulation is working properly. Thus we have that the total current through the low voltage side is 3000 A, as seen in Figure 9b. But like this current is the current through the source V in , so total power supplied by this source is 3 MW, which is can be seen as a wind turbine. Figure 9c shows that current in the high voltage side is the current predicted. It is necessary also, to check the values of d to check if it is correct for each module.As shown in Figure 9d the value of d is correct and it is stabilized at steady state. Now we check the value of high voltage side. So we can conclude that our control for the multilevel converter 1 kV / 150 kV is a good solution to solve the problem. One of the main aspects of the proposed control is that the philosophy of control for a multilevel converter of n modules is always the same, it consits in carry out an individual control of each module, with a current reference (could be different) for each module. The usual way of working is that all modules have the same reference, but there may be situations where different references are required; this is not a problem from the standpoint of control because, as said, control philosophy is individual for each module. A possible practical use is shown in Figure 10, which it shows an HVDC network composed of a solar installation, a wind farm and a storage. The HVDC network is connected to the global AC network. Individually control to each subsystem of HVDC network allows that the global system works satisfactory even if there is a failure in some subsystem. So the control is very robust, and it can be applied in many situations. The main output of this paper is to provide DC/DC transformer solution renewable energy integration into multi-terminals DC grid. Two important requirements need to be satisfied: high voltage ratio between input and output DC transformer and bidirectional functionality of the converter. Three main topologies to perform DC/DC conversion have been reviewed in this work which all of them have advantages and drawbacks. Thanks to its simplicity and cost efficiency compared with others, the DAB converter has been chosen to perform DC-DC conversion as single transformer module and in multilevel configuration for DC grid applications. In this paper interesting multilevel approach has been proposed with multi-sources inputs where different technologies of power production and storage systems could be connected. This approach seems interesting in terms of coast and redundancy, since that each DC/DC transformer module is contributing to make the needed output voltage. Each module can contain the desired type of DC/DC bi-directional converter; however it is always advisable to have the same module in each converter, unless the structure has been developed in plug and play manner. All these advantages make the multilevel converter a good alternative in wind energy applications as it helps to fulfill the objectives of improved quality in the generated energy, and allows greater working powers to be reached whilst minimizing losses. Also, modelling and control of DAB converter have been proposed in this deliverable. Steady state average current analytic expression has given to help users in finding the current permanent values for all operations of the DAB converter. A piecewise averaging technique is adopted to model the DAB converter. This technique seems to be more suitable for our application. Based on this piecewise average dynamic model, nonlinear robust control law is derived. The obtained control algorithm has been tested in closed-loop, at first on the nonlinear average dynamic model, and then on the real electrical circuit representing the DAB converter. Simulation results have been presented to highlight the good performances of the proposed control algorithm. Once a robust control algorithm has been developed for DAB converter, our aim was to propose a multilevel "Plug & Play" structure with DAB module association capable of elevating the voltage output. It should be pointed out that the DAB module considered here is made of the DAB converter with its control system. Simulation results in multilevel configurations have been proposed to show the effectiveness and performances in terms of dynamic response and robustness of the proposed control algorithm. The control design has been derived under the so-called "Plug & Play" philosophy.

Figure 1 :

 1 Figure 1: General scheme of installation.

Figure 2 :

 2 Figure 2: a) Structure of DAB. b) Structure of SRC. c) Structure of DHB.

Figure 3 :

 3 Figure 3: Building block multilevel DC transformer structure.

Figure 4 :

 4 Figure 4: DAB module Simplified circuit.

Figure 5 :

 5 Figure 5: Voltages and currents in the DAB circuit (d > 0).

  To verify that the differential equation have a properly behavior, we have created a file in SIMULINK to simulate the DAB bidirectional converter. The values of the simulation are shown in TableII

Figure 6 :

 6 Figure 6: Comparison between real DAB (mean value i 1 ) and the dynamic average model for d=0.15.

Figure 7 :

 7 Figure 7: a) Current response b) d response

Figure 8 :

 8 Figure 8: Multilevel converter with 3MW transmitted power

Figure 9 :

 9 Figure 9: a) Current though the left side in the n t h cell b) Current in low voltage side c) Current in high voltage side d) d response in n t h cell.

Figure 10

 10 Figure 10: HVDC network

Table I :

 I Advantages and drawbacks of each topology.

		DAB	SRC	DHB
	Advantages	Electrical Insulation	Electrical Insulation	Electrical Insulation
		Soft switching in primary and secondary circuits	Soft switching in primary and secondary circuits	Soft switching both circuits
		Resonant inductance built into transformer	Sinusoidal currents	Uses less devices
		Less reactive power	Inductance leakage is not a problem	Transformer flux swing lower
	Drawbacks	Soft switching may be lost at light load	Large resonant inductor (series inductance)	More reactive power
		Eight active power switches and control complex	High-voltage and high-current resonant capacitors	MOSFETs voltage limitation
		High ripple current in C 2 and large inductance leakage	Control complex	High current through the transformer
		Transformer saturation⇒ small capacitor in series	Variable frequency	Complex control algorithm

Table II :

 II Verification of differential equation. Simulation values.

	d	Phase shift ratio	0.15
	n	Transformer ratio	100/11
	R total	Total resistance	0.01Ω
	V in	Input voltage	1000 V
	V on	Output voltage	10000 V
	L	Inductance	6.875•10 -5 H
	T	Period	1/20000 s

This work is supported by WINPOWER project (ANR-10-SEGI-016).