Raphael Cardoso
email: raphael.cardoso@ec-lyon.fr

Clément Zrounba

Mohab Abdalla

Paul Jimenez

Mauricio Gomes De Queiroz

Benoît Charbonnier

Fabio Pavanello

Ian O'connor

Sébastien Le Beux

Towards

Robust Multiply

Towards a Robust Multiply-Accumulate Cell in Photonics using Phase-Change Materials

Keywords: photonic computing, phase-change memories, stochastic computing, computation-in-memory

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Following the needs of electronic crossbars for multiplyaccumulate (MAC) operations in AI applications, photonic approaches are being investigated with the promise of improvements in operation speed due to the unmatched parallelism achieved with light [START_REF] Peserico | Integrated photonic tensor processing unit for a matrix multiply: a review[END_REF]. Amongst photonic MAC alternatives, most are interference-based, which utilize large, power-hungry phase-shifters to compute [START_REF] Peserico | Integrated photonic tensor processing unit for a matrix multiply: a review[END_REF]. On the other hand, optical phase-change materials (PCMs) offer a small footprint, nonvolatile alternative [START_REF] Feldmann | Parallel convolutional processing using an integrated photonic tensor core[END_REF]. As shown in Fig. 1a, this method is based on the multiplicative interaction between the state of a PCM, i.e. the distribution of amorphous/crystalline phase, and the amplitude of an optical pulse. Thus we refer to it as amplitude-oPCM.

An important parameter for computing with PCMs is the number of intermediate states that it allows. Currently, up to 64 states (6 bits) have been demonstrated [START_REF] Wu | Programmable phase-change metasurfaces on waveguides for multimode photonic convolutional neural network[END_REF]. As new devices with higher bit counts become available, it is intuitive to expect better precision from them. However, in this paper we show that amplitude-oPCM actually degrades in accuracy as more bits are available in the presence of small perturbations. Besides, this approach further requires: i) precise adjustments of input intensity, ii) precise writing of values to the multilevel memory, iii) multi-wavelength light sources for MAC implementation. In this context, we propose stochastic-oPCM, This work was funded by Agence Nationale de la Recherche (ANR) under grant no. ANR-20-CE24-0019 (OCTANE). a single-wavelength approach that requires only 1-bit modulators, and thus does not depend on the precise adjustment of either the light pulses or the memory state. Our approach operates by continuously updating the accumulated values in the PCM state, therefore the results are automatically written in memory. To achieve multiplication, we rely on stochastic computing, which also includes error in the system, thus we compare the accuracy of both methods in the presence of small output perturbations, that could be caused by receiver electronics noise or temperature fluctuations.

II. PROPOSED APPROACH

A. Stochastic-oPCM Cell

In stochastic computing, data is converted to pseudo-random bitstreams using stochastic number generators (SNGs). Multiplication is performed by feeding these bitstreams to an AND gate and an accumulator, as seen in Fig. 1b. If the inputs are uncorrelated, the accumulated 1s will represent the product between the inputs, with additional error due to the approach's randomness [START_REF] Alaghi | Survey of stochastic computing[END_REF]. In photonics, a PCM deposited on top of a waveguide crossing can act as both the AND gate and the accumulator. To do so, we split a short, high power amorphizing pulse between the two branches of the crossing as seen in Fig. 1c, each carrying a stochastic bistream encoded by a one-bit optical modulator. Therefore, if two 1s arrive simultaneously, the PCM will partially amorphize, performing the AND operation [START_REF] Feldmann | Calculating with light using a chip-scale all-optical abacus[END_REF]. This operation is cumulative, so subsequent pulses will amorphize other parts of the material as illustrated in Fig. 1d. A disadvantage of this approach is that thermodynamic equilibrium must be reached between melting events, incurring a nanosecond delay between pulses [START_REF] Teo | Programmable chalcogenide-based all-optical deep neural networks[END_REF]. Finally, the transmission through an optical PCM depends on its state (inset of Fig. 1a), therefore we send a non-melting pulse with known amplitude to recover the result.

B. Simulation Environment and Methodology

We implemented a behavioral simulation environment in Python based on results from multiphysics simulations of a Ge 2 Sb 2 Te 5 thin film of 100 nm×250 nm×20 nm deposited on a 400 nm × 180 nm silicon waveguide. This PCM requires an optical pulse of 13.6 mW and 500 ps to amorphize one step.

For stochastic-oPCM, each 1 in a bitstream is encoded with 6.8 mW and thus we assume that the PCM state behaves as a discrete counter of amorphizing events with the transmission characteristic from Fig. 1a. To avoid corrupting the memory state at the end of operation, we use a non-melting readout pulse of 1.36 mW.

For amplitude-oPCM, we model the PCM as an attenuator with input-dependent transmission corresponding to the graphic in Fig. 1a. Input B is encoded linearly as an optical pulse between 0 and 1.36 mW. Optical losses are not considered in the simulations as they do not affect the precision, but rather the required laser power. The results are recovered from a look-up table obtained from unperturbed simulations.

III. SIMULATION RESULTS AND DISCUSSION

All tests in this section represent the average of 100 simulations of scalar multiplication considering 8-bit values, quantized down to 6 bits. Initially, in Fig. 1e, we demonstrate the sensitivity of amplitude-oPCM with three examples without perturbations: ( 1 ) two largely different products result in a similar output power, differing only by 0.6 µW, ( 2 ) two similar products produce largely different outputs, ( 3 ) multiplication is not commutative. When all the powers are exact, the correct output for any input can be recovered from the look-up table, as shown in Fig. 1f, in which the error comes only from quantization. However, as soon as we include a normally distributed perturbation with standard deviation of 1.36 µW, 0.1% of the readout power, high relative error peaks appear, surpassing 600%.

We also performed the same simulations for stochastic-oPCM, as shown in Fig. 1g. We observe that it also produces error, especially for small inputs and almost entirely due to the stochastic paradigm, as the behavior barely changes when perturbations are included. Lastly, we verify the average error of all operations for different bit quantizations, i.e. using PCMs with fewer levels, with results shown in Fig. 1h. In this case, we note that amplitude-oPCM achieves minimum error for 3 bits, due to quantization alone, but quickly degrades to 145% average error with 6 bits. On the other hand, stochastic-oPCM improves with more levels due to longer bitstreams [START_REF] Alaghi | Survey of stochastic computing[END_REF], reaching 21% average error with 6 bits.

IV. CONCLUSIONS

We propose a novel approach to achieve MAC operations in photonics using PCMs that requires less complex control than the state-of-the-art. We show that our method's accuracy is more robust to small perturbations. The proposed approach also includes error in the operation due to the nature of stochastic computing, and reducing it requires longer bitstreams, and thus PCMs with higher level counts. In future work, we intend to validate our assumptions with experimental data. Furthermore, we shall investigate how the stochastic-oPCM cell can be used in Computation-In-Memory architectures, taking advantage of its unique characteristic of automatically writing the result to memory.

Fig. 1 .

 1 Fig. 1. (a) Scalar multiplication with amplitude-oPCM. Inset: PCM transmission characteristic based on its state, (b) multiplication in stochastic computing with digital components, (c) cell for stochastic-oPCM multiplication, (d) PCM state evolution during stochastic-oPCM operation, (e) amplitude-oPCM operation for three cases, (f) relative error (%) of all operations in amplitude-oPCM multiplication, relative error (%) for all operations in stochastic-oPCM, (h) average relative error for both methods with different quantizations.

  Towards a Robust Multiply-Accumulate Cell in Photonics using Phase-Change Materials Raphael Cardoso 1 * , Clément Zrounba 1 , Mohab Abdalla 12 , Paul Jimenez 1 , Mauricio Gomes de Queiroz 1 , Benoît Charbonnier 3 , Fabio Pavanello 1 , Ian O'Connor 1 , Sébastien Le Beux 4


Bianca Marin Moreno

Margaux Brégère

Pierre Gaillard

Nadia Oudjane

Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent

Many machine learning tasks can be solved by minimizing a convex function of an occupancy measure over the policies that generate them. These include reinforcement learning, imitation learning, among others. This more general paradigm is called the Concave Utility Reinforcement Learning problem (CURL). Since CURL invalidates classical Bellman equations, it requires new algorithms. We introduce MD-CURL, a new algorithm for CURL in a finite horizon Markov decision process. MD-CURL is inspired by mirror descent and uses a non-standard regularization to achieve convergence guarantees and a simple closed-form solution, eliminating the need for computationally expensive projection steps typically found in mirror descent approaches. We then extend CURL to an online learning scenario and present Greedy MD-CURL, a new method adapting MD-CURL to an online, episode-based setting with partially unknown dynamics. Like MD-CURL, the online version Greedy MD-CURL benefits from low computational complexity, while guaranteeing sub-linear or even logarithmic regret, depending on the level of information available on the underlying dynamics.

Introduction

We consider the concave utility reinforcement learning (CURL) problem, which consists on minimizing a convex function (or maximising a concave one) over Under review.

state-action distributions induced by an agent's policy:

min π∈(∆ A ) X ×N F (µ π,p ) := N n=1 f n (µ π,p n ) . (1)
Here, we consider an episodic Markov decision process (MDP) with finite state space X , finite action space A, episodes of length N , and probability transition kernel p := (p n ) n∈ [N ] such that p n : X × A × X → [0, 1]. For all s ∈ N we denote [s] := {1, . . . , s}. Letting ∆ S be the simplex over a finite set S, we denote µ π,p := (µ n ) 0≤n≤N ∈ (∆ X ×A ) N the state-action distributions over an episode induced by the policy π in the MDP with dynamics p.

Many machine learning tasks are special cases of Problem (1). For instance, for the reinforcement learning (RL) task [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], F (µ π,p ) := -µ π,p , r , i.e. the inner product between the stateaction distribution induced by π and a reward r.

For the imitation learning problem [START_REF] Ghasemipour | A divergence minimization perspective on imitation learning methods[END_REF], F (µ π,p ) := D f (µ π,p , µ * ), where D f represents a Bregman divergence induced by a function f . For some instances of the mean field control (MFC) problem [START_REF] Bensoussan | Mean Field Games and Mean Field Type Control Theory[END_REF], F (µ π,p ) := -µ π,p , r(µ π,p ) , where the reward function also depends on the agents' state-action distribution. For mean field game (MFG) problems having the gradient of F as reward, finding a Nash Equilibrium amounts to solving Problem (1) [START_REF] Geist | Concave utility reinforcement learning: The mean-field game viewpoint[END_REF][START_REF] Lavigne | Generalized conditional gradient and learning in potential mean field games[END_REF].

Contribution 1: We present a new iterative algorithm focusing on solving Problem (1) called MD-CURL. It is inspired by the mirror descent algorithm [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF], and we prove a convergence rate of order 1/ √ K where K is the number of iterations. Our main new ingredient is the use of a non-standard regularization, which enables us to find both a simple closed-form solution -meaning we avoid the generally costly projection step that mirror descent algorithms undergo -and a convergence proof.

Until now, there have been few algorithms for solving the general framework of Problem (1). The first two approaches were proposed, by [START_REF] Hazan | Provably efficient maximum entropy exploration[END_REF] on the basis of the Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Frank | An algorithm for quadratic programming[END_REF]Zhang et al. (2020) on the basis of policy gradient methods, both of which have theoretical guarantees. In the mean field community, [START_REF] Geist | Concave utility reinforcement learning: The mean-field game viewpoint[END_REF] prove that all algorithms for solving MFGs in discrete-time RL can be applied for solving CURL. [START_REF] Laurière | Learning mean field games: A survey[END_REF] survey existing algorithms and perform numerical experiments, showing that the adaptation of online mirror descent (OMD) for MFGs presented by [START_REF] Pérolat | Scaling mean field games by online mirror descent[END_REF] has the best performance, outperforming the previously mentioned approaches. However, this method has no proof of convergence for discrete iterations. Our proposed algorithm, as we demonstrate with showcase experiments, has the same performance as OMD for MFGs while having theoretical guarantees of convergence.

Online extension of CURL: An interesting extension of Problem (1) is the online learning scenario, in which we consider computing a sequence of policies (π t ) t∈[T ] for T episodes with the objective of minimizing a total loss

L T := T t=1 F t (µ π t ,p ), (2)
where we allow the objective function F t to change arbitrarily over time (and only be revealed at the end of each episode t).

Here, we consider dynamics such that (x 0 , a 0 ) ∼ µ 0 (•), and for all steps n ∈ [N ],

x n+1 := g n (x n , a n , ε n ),

where (ε n ) n∈[N ] is an independent sequence of external noises with ε n ∼ h n (•) for h n a distribution.

Different variants of this problem can be considered, depending on the prior information available on the dynamics. Here, we consider the case where the agent has prior knowledge of the dynamics (g n is known), but may be subject to unknown external interference (h n is unknown). This includes scenarios such as: An energy central controlling the average consumption of electrical appliances. The temperature evolution equation is known, but consumer behavior is unknown and can interfere with the dynamics [START_REF] Coffman | A unified framework for coordination of thermostatically controlled loads[END_REF]. Controlling a fleet of drones in a known environment, subject to external influences due to weather conditions or human intervention. Controlling the state of charge of electric vehicles so that their average consumption follows an energy production target that changes every day and is not known in advance. The dynamics of loading are known, but the arrival and departure of users are not (Séguret et al., 2021).

Contribution 2: We propose Greedy MD-CURL, an online learning algorithm for CURL with dynamics as in Equation (3) when g n is known but the noise distribution h n is unknown. At each episode, we play a policy π t , observe the agent's behavior, update an estimate of the external noise, and use the estimated dynamics to compute the next policy using MD-CURL. Greedy MD-CURL achieves state-of-theart sub-linear regrets with low complexity and simple closed-form solutions. We further avoid the |X | term paid in UCRL approaches (see Section 2) by showing a weaker control on the difference between the true and estimated probability kernels, being an advantage for models with large state spaces.

Balancing exploration and exploitation is challenging when both g n and h n are unknown, which can be computationally expensive. Greedy MD-CURL offers a low-complexity algorithm that achieves sublinear regret, even without explicit exploration (see Remark 5.3). Although its regret bound is not the state of the art, Greedy MD-CURL is a good option for scenarios where exploration is already induced by the objective function or by noisy models.

Related Work

Online MDPs have mostly been studied in specific cases of CURL rather than in its general form, and draw inspiration from online learning problems [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. In model-based RL [START_REF] Even-Dar | Online markov decision processes[END_REF] were the first to propose a method dealing with adversarial functions, supposing the transition kernel is fully known in advance. [START_REF] Neu | The adversarial stochastic shortest path problem with unknown transition probabilities[END_REF] extended this work to the case of unknown transition kernels with adversarial rewards, using techniques inspired by UCRL-2 (Upper Confidence Reinforcement Learning) [START_REF] Jaksch | Nearoptimal regret bounds for reinforcement learning[END_REF]. Recently, UC-O-REPS was proposed by [START_REF] Rosenberg | Online convex optimization in adversarial Markov decision processes[END_REF], which extends Zimin and Neu (2013) O-REPS algorithm to the case of unknown dynamics and improves upon the regret bound of [START_REF] Neu | The adversarial stochastic shortest path problem with unknown transition probabilities[END_REF].

In the mean-field community, most approaches for unknown dynamics consider model-free scenarios, such as [START_REF] Angiuli | Unified reinforcement q-learning for mean field game and control problems[END_REF][START_REF] Angiuli | Reinforcement Learning for Mean Field Games, with Applications to Economics[END_REF]; [START_REF] Carmona | Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games: II-the finite horizon case[END_REF]. M3-UCRL, proposed by [START_REF] Pasztor | Efficient model-based multi-agent mean-field reinforcement learning[END_REF], is the only model-based algorithm for mean-field control problems with unknown dynamics. It uses the principle of optimism under uncertainty with UCRL-2 techniques, but only provides regret bounds for Gaussian process dynamics and does not consider online adversarial objective functions.

We introduce the first algorithm for the online CURL problem with theoretical guarantees. Unlike UCRL and PSRL approaches [START_REF] Osband | more) efficient reinforcement learning via posterior sampling[END_REF], which are generally computationally expensive, our algorithm is nearly greedy and still achieves the same regret bounds with lower computational complexity, depending on the dynamics information available.

General Problem Formulation

Consider an episodic Markov decision process (MDP) with finite state space X , finite action space A, episodes of length N , and a sequence of transition probabilities p := (p n ) n∈ [N ] where

p n : X × A × X → [0, 1].
π := (π n ) n∈[N ]
, we define µ π,p := (µ π,p n ) 0≤n≤N the state-action distribution sequence induced by the policy π in the MDP with probability kernel p recursively for all (x , a ) ∈ X × A and all n ∈ [N ]:

µ π,p 0 (x , a ) := µ 0 (x , a ) (4) µ π,p n (x , a ) := x∈X a∈A µ π,p n-1 (x, a)p n (x |x, a)π n (a |x ).
We let • 1 be the L 1 norm, and for all

v := (v n ) n∈[N ] , such that v n ∈ R X ×A we define v ∞,1 := sup 0≤n≤N v n 1 .
We define the objective function F (µ) := N n=1 f n (µ n ) where f n : ∆ X ×A → R are convex and -Lipschitz functions with respect to the norm • 1 .

Offline optimization setting (Section 4) To solve the CURL problem, we propose a learning protocol that consists in following an iterative method. At each iteration k ∈ [K], the learner computes a new policy by solving an auxiliary optimization problem. This auxiliary optimization problem, that we denote by F, depends on the previous policy π k-1 , the model dynamics p, and the objective function F , i.e. π k := F(π k-1 , p, F ). In Section 4, we show how to construct F such that min k∈[K] F (µ π k ,p ) -F (µ π * ,p ) is bounded by a term of order 1/ √ K, with K the number of iterations, where π * is an optimal policy.

Online learning setting (Section 5) In the online extension of CURL, the objective function at episode t ∈ [T ] is denoted as

F t := N n=1 f t
n , where T is the total number of episodes, and f t n : ∆ X ×A → R. We assume that f t n is convex and -Lipschitz with respect to the • 1 norm. The functions F t are only revealed to the learner at the end of episode t. The learner's objective is to compute a sequence of strategies (π t ) t∈ [T ] minimizing their total loss defined in Equation ( 2), and the learner's performance is measured by comparison to the best stationary policy, using the following regret:

R T := T t=1 F t (µ π t ,p ) - min π∈(∆ A ) X ×N T t=1
F t (µ π,p ). ( 5)

We consider the dynamics of Equation (3) when g n is known but h n is unknown. In order to choose a sequence of policies that minimize their total loss, the learner must then both optimize the objective function and learn the noise distribution through observations. The learner's online protocol is in Algorithm 1.

At each episode t, the learner chooses a policy π t , send it to M independent agents, observes the external noise (ε j,t 1 , . . . , ε j,t N ) for each agent j ∈ [M ] over all N steps (to retrieve the noises, it is enough to observe the agent's trajectory and for g n to be invertible), computes an estimate pt+1 of the probability kernel using the observations, observes the objective function F t , and calculates the policy for the next episode by applying the auxiliary problem F on π t , F t , and pt+1 .

To compute a strategy sequence with sub-linear regret the learner faces two challenges: how to estimate pt from the data and how to define the auxiliary optimization problem F. In Section 5, we show that by considering the same auxiliary optimization problem F as in the optimization of the offline CURL problem, and by taking pt+1 as the empirical mean estimator, we can build an algorithm that achieves sub-linear regret. This result is studied in detail in Section 5. Observing M independent agents following the same policy is relevant to many applications, such as controlling the charging state of a set of electric vehicles. This allows us to explicitly express the dependence on M . Note that if we set M = 1, we recover the standard case.

CURL as an optimisation problem

Reformulation of learner's objective

The CURL problem as presented in Equation ( 1) is problematic in that it is not convex in π, and calculating the gradient of F with respect to the strategy π can be intractable. Therefore, we reformulate the learner's objective to obtain a convex problem. We define

M p µ0 := µ ∈ (∆ X ×A ) N a ∈A µ n (x , a ) = (6) x∈X ,a∈A p n (x |x, a)µ n-1 (x, a) , ∀x ∈ X , ∀n ∈ [N ] ,
Algorithm 1 Learner's Online Protocol

Input: initial state-action distribution µ 0 , initial strategy sequence π 1 . for t = 1, . . . , T do for j = 1, . . . , M do the j-th agent playing episode t starts at (x j,t 0 , a j,t 0 ) ∼ µ 0 (•) for n = 1, . . . , N do environment draws new state x j,t n ∼ p n (•|x j,t n-1 , a j,t n-1 ) learner observes agent's j external noise ε j,t n agent j chooses an action a j,t n ∼ π t n (•|x j,t n ) end for end for learner computes, for all n ∈ [N ], new estimate pt+1

n from data (ε j,s n ) s∈[t]
,j∈[M ] objective function F t is exposed learner computes π t+1 = F(π t , pt+1 , F t ) and send to all agents end for return π T as the set of state-action distribution sequences satisfying the Bellman-flow in the MDP with transition kernel p and initial state-action distribution µ 0 . For now, we assume that the probability kernel p is known and, to minimize notations, we let µ π := µ π,p and M µ0 := M p µ0 . We also assume µ 0 is always known. For any µ ∈ M p µ0 , there exists a strategy π such that µ π = µ. It suffices to take π n (a|x) ∝ µ n (x, a) when the normalization factor is non-zero, and arbitrarily defined otherwise. This result is formally enunciated and proved in Proposition A.1 in Appendix A (see also [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]). We therefore have the equivalence

min π∈(∆ A ) X ×N F (µ π ) ≡ min µ∈Mµ 0 F (µ).
Note that the optimization problem over µ is convex.

The Algorithm

To build an algorithm solving the CURL problem, we need to build the auxiliary optimization problem F discussed in Section 3. Let M * µ0 denote the subset of M µ0 where the corresponding policies π are such that π n (a|x) = 0 for all (x, a) ∈ X × A, n ∈ [N ]. We define a regularization function Γ :

M µ0 × M * µ0 → R as Γ(µ π , µ π ) := N n=1 E (x,a)∼µ π n (•) log π n (a|x) π n (a|x) , (7)
that is well defined thanks to the bijection between strategies and state-action distributions satisfying the Bellman flow (see Proposition A.1). We define the following iterative scheme with τ k > 0 and

∇F (µ k ), µ π := N n=1 ∇f n (µ k n ), µ π n : µ k+1 ∈ arg min µ π ∈Mµ 0 ∇F (µ k ), µ π + 1 τ k Γ(µ π , µ k ) , (8)
where the idea is, at iteration k +1, to choose µ π minimizing a linearization of the objective function around µ k , the distribution sequence found at the previous iteration, and at the same time penalizing the distance between policy π inducing µ π and π k inducing µ k . Our first main result of this section is in Theorem 4.1. It shows that, due to the choice of penalizing strategies, the iterative scheme in Equation ( 8) can be solved through dynamic programming [START_REF] Bertsekas | Dynamic Programming and Optimal Control, volume I[END_REF] by building a Bellman recursion:

Theorem 4.1. Let k ≥ 0. The solution of Prob- lem (8) is µ k+1 = µ π k+1
, where for all n ∈ [N ], and (x, a) ∈ X × A,

π k+1 n (a|x) := π k n (a|x) exp(τ k Qk n (x,a)) a ∈A π k n (a |x) exp(τ k Qk n (x,a )) , (9) where Q is a regularized Q-function satisfying the fol- lowing recursion Qk N (x, a) = -∇f N (µ k N )(x, a) Qk n (x, a) = max πn+1∈(∆ A ) X -∇f n (µ k n )(x, a)+ x p n+1 (x |x, a) a π n+1 (a |x ) (10) - 1 τ k log π n+1 (a |x ) π k n+1 (a |x ) + Qk n+1 (x , a ) .
Proof. See Appendix B.1.

It is not obvious at first sight, but we can show that Γ is a Bregman divergence, making the iterative scheme an instance of mirror descent [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF]. Therefore, we can state the convergence result of Algorithm 2, MD-CURL, in Theorem 4.2, the second main result of this section. Solving a mirror descent (MD) instance usually includes a projection step that is generally computationally expensive. The low-complexity methods existing in the literature can only offer approximate solutions [START_REF] Dick | Online learning in markov decision processes with changing cost sequences[END_REF][START_REF] Rosenberg | Online convex optimization in adversarial Markov decision processes[END_REF]. We show that with the judicious choice of divergence as in Equation ( 8), MD can be solved accurately avoiding all costly projection steps. Theorem 4.2. Let π * be a minimizer of Problem (1).

Define L := N where is the Lipschitz constant of f n with respect to • 1 for all n ∈ [N ]. Applying K iterations of MD-CURL to this problem, with, for each 1 ≤ k ≤ K, τ k := L -1 2Γ(µ π * , µ 0 )/K, gives the following convergence rate

min 0≤k≤K F (µ π k ) -F (µ π * ) ≤ L 2Γ(µ π * , µ 0 ) √ K .
Algorithm 2 MD-CURL

1: Input: number of iterations K, initial se- quence of policies π 0 ∈ (∆ A ) X ×N such that µ 0 := µ π0 ∈ M * µ0 , objective function F := N n=1 f n , probability kernel p = (p n ) n∈[N ]
, initial state-action distribution µ 0 , sequence of nonnegative learning rates (τ k ) k≤K . 2: for k = 0, . . . , K -1 do 3:

µ k = µ π k as in Equation (4) 4: Qk N (x, a) = -∇f N (µ k N )(x, a), ∀(x, a) ∈ X × A 5:
for n = N, . . . , 1 do 6:

∀(x, a) ∈ X × A :

7:

π k+1 n (a|x) = π k n (a|x) exp(τ k Qk n (x,a)) a π k n (a |x) exp(τ k Qk n (x,a ))
8:

Qk n-1 (x, a) using the recursion in Equation (10)

9:
end for 10: end for 11: return π K Proof. For ease of notation, for any probability measure η ∈ ∆ E , whatever the (finite) space E, we introduce the neg-entropy function, with the convention that 0 log(0) = 0, φ(η) := x∈E η(x) log η(x).

Proposition 4.3. Let µ ∈ M µ0 with marginal given by ρ ∈ (∆ X ) N . The divergence Γ is a Bregman divergence induced by

ψ(µ) := N n=1 φ(µ n ) - N n=1 φ(ρ n ).
Also, ψ is 1-strongly convex with respect to • ∞,1 .

The proof is in Appendix B.2 and consists in showing that the Γ divergence taking values on the sequence of state-action distributions is in fact the KL divergence on the joint distribution. Next, if f n is convex and -Lipschitz with respect to the norm • 1 for all n ∈ [N ], then F is also convex and Lipschitz with constant L := N with respect to the norm • ∞,1 (see Appendix B.2). Since the set M µ0 is convex, all convergence assumptions of MD [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF] are satisfied, and the rate of convergence follows.

Online learning extension of CURL

We consider here the online variant of Problem (1), where the learner must compute a sequence of strategies while facing unknown external noise and arbitrarily changing objective functions. We introduce Greedy MD-CURL, a new algorithm achieving sub-linear regret with a simple closed-form solution. At episode t, Greedy MD-CURL solves an optimization problem in the MDP induced by the estimated probability kernel pt using one iteration of MD-CURL. We refer to p as the true probability kernel and pt as the estimated one.

Learning the model

Since the learner does not know the noise dynamics, it has to estimate it from its experience. To obtain a sub-linear regret, the learner must learn pt in such a way that its distance to the real probability kernel decreases with t with high probability. Let us denote M t n the number of times the learner observes step n until the start of episode t, and ε s n the s-th noise observed at step n. Recall that the dynamics follow Equation (3), and that the learner observes the noise values from the agent's trajectory. Let δ x be the Dirac distribution centered in x. We define

pt n (•|x, a) := 1 M t n M t n s=1 δ gn(x,a,ε s n ) (•). ( 11
)
For any function Λ : X → R, for all n ∈ [N ] and (x, a) ∈ X × A we introduce the notation

p n -p t n Λ (x, a) := x ∈X p n (x |x, a)-p t n (x |x, a) Λ(x ).
We have the following concentration result.

Lemma 5.1. Let γ > 0. For any 0 < δ < 1 and any function Λ :

X → R such that |Λ(x )| ≤ √ γ/2 for all x ∈ X , p n -pt n Λ (x, a) ≤ γ 2M t n log N |X ||A|T δ holds with probability 1 -δ simultaneously for all (x, a) ∈ X × A, steps n ∈ [N ], and episodes t ∈ [T ].
Proof. See Appendix C.1.

In the literature [START_REF] Jaksch | Nearoptimal regret bounds for reinforcement learning[END_REF][START_REF] Rosenberg | Online convex optimization in adversarial Markov decision processes[END_REF], it is common to bound the L 1 deviation between p and pt instead. However, this deteriorates the bound by an additional factor of |X |, which we can avoid here because of our dynamics hypothesis. This means that in the final regret analysis, we only pay the number of states in a term proportional to log(|X |), which is an advantage for problems with large state spaces or even to discretize continuous state space problems.

We further state Lemma 5.2, which is proven in Appendix C.2 and used later to prove the regret bound of Greedy MD-CURL.

Lemma 5.2. For any vector v ∈ R |X |×|A| , for any strategy π and for all 0

≤ n ≤ N , v, µ π,p n -µ π, pt n = n i=1 y∈X ×A µ π, pt i-1 (y) p i -pt i (Λ i,n,π v )(y),
where

Λ i,n,π v : X → R is a function depending on v, i, n and π defined in Equation (25). Also, if v ∞ := sup (x,a)∈X ×A |v(x, a)| ≤ V , then Λ i,n,π v ∞ ≤ V .

Optimization problem

Recall that the learner follows the online protocol in Algorithm 1. At each episode, the learner estimates pt from the noise observations using Equation ( 11), We denote by M t µ0 := M pt µ0 the set induced by this estimate (as in Equation ( 6)). At every episode the learner solves

µ t+1 ∈ arg min µ∈M t+1 µ 0 {τ ∇F t (µ t ), µ + Γ(µ, μt )}, (12)
where, µ t := µ π t , pt and μt := µ πt , pt with

πt := (1 -α t )π t + αt |A| , (13)
and α t ∈ (0, 1/2) is an exploration parameter.

In Theorem 4.1, we have already shown that the optimization problem of Equation ( 12) with Bregman divergence Γ has the format of an exponential twist as in Equation ( 9). Consequently, we can build Greedy MD-CURL in Algorithm 3. Note that to compute the policy for episode t + 1, we perform one iteration of MD-CURL using π t to compute µ t as in line 3 of Algorithm 2, πt to compute the exponential twist in line 7 and to compute Q recursively in line 8, the objective function F t and the estimated probability kernel pt+1 .

Remark 5.3. We call our algorithm Greedy because it solves the optimization problem (12) at each episode using the empirically estimated dynamics (11) as if they were the true ones, without confidence intervals or exploration bonuses related to visit counts as usually is the case [START_REF] Jaksch | Nearoptimal regret bounds for reinforcement learning[END_REF][START_REF] Rosenberg | Online convex optimization in adversarial Markov decision processes[END_REF][START_REF] Azar | Minimax regret bounds for reinforcement learning[END_REF].

Regret analysis

In this section, we prove the regret bound of Greedy MD-CURL. For that, we use the results from Subsection 5.1 and some results of OMD (Shalev-Shwartz, 2012), while also having to handle an online optimization problem with varying constraint sets. We decompose the regret (5) into three terms,

R T = T t=1 F t (µ π t ,p ) -F t (µ π t , pt ) + T t=1 F t (µ π t , pt ) -F t (µ π * , pt+1 ) + T t=1 F t (µ π * , pt+1 ) -F t (µ π * ,p ) := R M DP T ((π t ) t∈[T ] ) + R policy T + R M DP T (π * ) , Algorithm 3 Greedy MD-CURL Input: number of episodes T , initial sequence of policies π 1 ∈ (∆ A ) X ×N , number of observations per episode M , initial state-action distribution µ 0 , learning rate τ > 0, sequence of parameters (α t ) t∈[T ] . Initialization: ∀(x, a), p 1 (•|x, a) = 1 |X |
for t = 1, . . . , T do for j = 1, . . . , M do j-th agent starts at (x j,t 0 , a j,t 0 ) ∼ µ 0 (•)

for n = 1, . . . , N do environment draws new state x j,t n ∼ p n (•|x j,t
n-1 , a j,t n-1 ) learner observes agent j's external noise ε j,t n agent j chooses an action a j,t n ∼ π t n (•|x j,t n ) end for end for update probability kernel estimate for all (x, a):

pt+1 n (•|x, a) := 1 M t M j=1 δ gn(x,a,ε j,t n ) + t -1 t pt n (•|x, a)
compute policy for the next episode:

π t+1 := MD-CURL(1, π t \π t , F t , pt+1 , µ 0 , τ ) compute πt+1 as in Equation (13) end for return (π t ) t∈[T ] where π * := arg min π∈(∆ A ) X ×N T t=1 F t (µ π,p ). The terms R M DP T ((π t ) t∈[T ]
) and R M DP T (π * ) pay for the error due to not knowing the true probability kernel, and the term R policy T pays for calculating sub-optimal policies using MD-CURL with constraint sets varying with each episode. Propositions 5.5 and 5.7 bound each of these terms, yielding our main result: Theorem 5.4. Consider an episodic MDP with finite state space X , finite action space A, episodes of length N , and probability kernel p :

= (p n ) n∈[N ] . Let F t := N n=1 f t n convex with f t n -Lipschitz with respect to the norm • 1 for all n ∈ [N ], t ∈ [T ]. Let b := T t=1 2 N α t + N 2 t log |A| αt + N 2 1 t + α t 2 + N log(|A|) 1 2 (14) Then, with probability 1 -δ, Greedy MD-CURL ob- tains, for τ = b L √ T , R T ≤ 2 N b √ T + 2 N 2 2T M log N |X ||A|T δ .
In particular, choosing

α t = T -1 for all t ∈ [T ], yields R T = O( √ T log(T )).
R M DP T (π t ) t∈[T ] ≤ N 2 2T M log N |X ||A|T δ .
The exact same result being also valid for R M DP T π * .

Proof. See Appendix C.3.

Bounding R policy T

The term R policy T pays for the loss associated with the convergence of MD-CURL. Our main challenge is to deal with the terms concerning variable constraint sets M t µ0 . They depend on a bound on the difference between the state-action distributions induced by two consecutive probability kernel estimates, i.e. µ π, pt -µ π, pt+1

∞,1 stated in Lemma 5.6. We also need a bound on ∇ψ(µ π,p ) ∞,1 , the function inducing the Bregman divergence, justifying our construction in Equation ( 13). The result is stated in Proposition 5.7.

Lemma 5.6. For any policy sequence π ∈ (∆ A ) X ×N , the estimation of the probability kernel for two consecutive episodes done by Greedy MD-CURL satisfies, for all episodes t ∈ [T -1], the following inequality

µ π, pt+1 -µ π, pt ∞,1 ≤ 2N t .
Proposition 5.7. Under the same hypothesis as in Theorem 5.4, let b be defined as in Equation ( 14).

Then, Greedy MD-CURL obtains, for

τ = b L √ T , R policy T ≤ 2 N b √ T .
Proof. See Appendix D.5.

Remark 5.8. Appendix E shows that Greedy MD-CURL also has sub-linear regret in T when both g n and h n are unknown and the learner observes the trajectory of state-action pairs that each agent follows. Although its regret is not the best in the state of the art, Greedy MD-CURL is a good option when exploration is already induced by the environment.

Showcase experiments

In this section, we evaluate the performance of MD-CURL and Greedy MD-CURL on the entropy maximisation and multi-objectives problems, both introduced by [START_REF] Geist | Concave utility reinforcement learning: The mean-field game viewpoint[END_REF]. To test Greedy MD-CURL's ability to learn the unknown dynamics, we consider a version with fixed, non-adversarial objective functions and the same probability kernel for all n ∈ [N ]. Appendix F provides further experimental results.

Environments

We consider a model where the state space is a 11 × 11 four-room dimensional grid world with a single door connecting adjacent rooms. At each step, the agent can choose to stay still, go right, left, up or down, provided that there are no walls in the way:

x n+1 = x n + a n + ε n , (15)
with a n ∈ {(0, 0), (0, 1), (1, 0), (-1, 0), (0, -1)}. The external noise ε n represents a perturbation that pushes the agent to a neighbor state with a certain probability. We suppose the initial distribution is a Dirac at the upper left corner of the grid as in Figure 1 [left].

Entropy maximisation At each step, f n (µ π,p n ) := ρ π,p n , log(ρ π,p n ) , where ρ π,p n (x) := a∈A µ π,p n (x, a). Thus minimizing F := N n=1 f n means maximizing the entropy, so the optimal value is when the distribution is uniform over the state space (obs.: contrary to intuition, the uniform policy does not provide an optimal solution, as can be seen in Figure 1,[middle]).

Multi-objectives

The goal is for the distribution to be concentrated on the three targets in Figure 1, [right], by the final step N . We let

f n (µ π,p n ) := - 3 k=1 (1 -ρ π,p n , e k ) 2
, where e k ∈ R |X | is a vector with zero everywhere and 1 in the element corresponding to a target state. Note that the target may not be reachable by any policy. 2022), but have no convergence results for discrete iterations. Therefore, MD-CURL is a good alternative for achieving state-of-the-art performance, with the advantage of having theoretical results. Note that both algorithms converge similarly, we leave the analysis of their differences for future work.

We now examine Greedy MD-CURL for online CURL.

We add a noise ε n that follows a categorical distribution h n , with a 0.2 probability of going up and 0 for other directions. We suppose g n is known but h n is unknown, and we take M = 10. Figure 4 compares the log regret per iteration for Greedy MD-CURL (blue), MD-CURL with known noise dynamics (green), and MD-CURL with unknown noise dynamics, where the learner never learns the noise distribution, i.e. pt n (•|x, a) = δ gn(x,a,0) for all (x, a) (red). We see that Greedy MD-CURL quickly matches MD-CURL with known noise dynamics, and that never learning the noise is sub-optimal. We do not compare Greedy MD-CURL to other algorithms in the literature as none is well-suited to our scenario, and the ones that could be adapted use UCRL techniques making them computationally expensive or intractable.

Finally, Greedy MD-CURL achieves sub-linear regret

Conclusion and future works

In this paper we analyzed two versions of the CURL problem in episodic MDPs with finite state and action spaces. For the offline optimization problem, where the dynamics g n and h n are known, we proposed an algorithm based on mirror descent converging with a rate of O 1/ √ K for K iterations. For the online learning extension with adversarial costs, we proposed an algorithm with a simple closed-form solution, and regret of O √ T log(T ) when g n is known but h n is unknown. Also, we showed that for this specific dynamic, we can improve the bounds of existing work and pay the number of states only in a term proportional to log(|X |).

A future direction is to investigate if we can achieve optimal regrets for variants of Greedy MD-CURL under more general assumptions about the available dynamics information. For example, by considering the case where g n is a parametric function with unknown parameters, rather than being completely known.

A Equivalence between policies and distributions in M µ

0 Proposition A.1. Let µ 0 ∈ ∆ X ×A . The application π → µ π is a bijection from (∆ A ) X ×N to M µ0 .
Proof. Consider a fixed initial state-action distribution µ 0 ∈ ∆ X ×A . Let µ ∈ M µ0 and define ρ = (ρ n ) 0≤n≤N such that for all x ∈ X , ρ n (x) = a µ n (x, a) (the associated state distribution). First, let us deal with the case where ρ n (x) = 0. Define a policy sequence π ∈ (∆ A ) X ×N such that π n (a|x) = µn(x,a) ρn(x) for all (x, a) ∈ X × A. We want to show that µ π = µ for this policy π. We reason by induction. For n = 0, µ π 0 = µ 0 by definition. Suppose µ π n = µ n , thus for n + 1 and for all (x , a ) ∈ X × A

µ π n+1 (x , a ) = x,a p n+1 (x |x, a)µ π n (x, a)π n+1 (a |x ) = x,a p n+1 (x |x, a)µ n (x, a) µ n+1 (x , a ) ρ n+1 (x ) = a µ n+1 (x , a) µ n+1 (x , a ) ρ n+1 (x ) = ρ n+1 (x ) µ n+1 (x , a ) ρ n+1 (x ) = µ n+1 (x , a ),
where the first equality comes from Equation (4), the second equality comes from the induction assumption and the way we defined the strategy π, and the third comes from the assumption that µ ∈ M µ0 .

In the case ρ n (x) = 0, we therefore have µ n (x, a) = 0 for all a ∈ A, so any choice of π n (a|x) would work. Because we want to make sure that there is a unique mapping from each π to µ π we agree to always set π n (a|x) = 1 |A| in this case, where |A| is the number of possible actions.

B Proofs of Section 4: algorithm 2 scheme and convergence rate

By abuse of notation, for any probability measure η ∈ ∆ E whatever the finite space E on which it is defined we introduce the neg-entropy function, with the convention 0 log(0) = 0,

φ(η) := x∈E η(x) log η(x), (16)
to which we associate the Bregman divergence D, also known as the KL divergence, such that for any pair

(η, ν) ∈ ∆ E × ∆ E , D(η, ν) := φ(η) -φ(ν) -∇φ(ν), η -ν .
Let ρ n denote the marginal probability distribution on X associated with µ n i.e., for all x ∈ X

ρ n (x) := a∈A µ n (x, a) .
Observe that to any µ = (µ n ) 1≤n≤N ∈ M µ0 one can associate a unique probability mass function on ∆ (X ×A) N denoted by µ 1:N such that µ 1:N is generated by the strategy π = (π n ) n∈[N ] associated with µ which is determined by

π n (a|x) = µ n (x, a) ρ n (x) ,
when ρ n (x) = 0, otherwise we fix an arbitrary strategy π n (a|x) = 1 |A| . Before proving Theorems 4.1 and 4.2 we state and prove a lemma which is key to proving both theorems.

Lemma B.1. For any µ ∈ M µ0 and µ ∈ M * µ0 , with associated probability mass functions µ 1:N , µ 1:N ∈ ∆ (X ×A) N generated by π, π respectively with the same initial state-action distribution, i.e. µ 0 = µ 0 , we have

D(µ 1:N , µ 1:N ) = Γ(µ, µ ) = N n=1 D(µ n , µ n ) - N n=1 D(ρ n , ρ n ), (17)
where Γ(µ, µ ) := N n=1 E (x,a)∼µn(•) log πn (a|x) π n (a|x)

.

Proof. For each n ∈ [N ], let us define a transition matrix P πn for all x, x ∈ X and a, a ∈ A,

P πn (x , a |x, a) := p n (x |x, a)π n (a |x ).
Given Definition 4, for any randomized policy the state-action distributions evolve according to linear dynamics

µ n (x , a ) = µ n-1 (•), P πn (x , a |•) .
Any randomized policy π induces a probability mass function µ 1:N that is Markovian:

µ 1:N ( y) = µ 0 (y 0 )P π1 (y 1 |y 0 ) . . . P π N (y N |y N -1 ), ( 18
)
where y represents the elements of (X × A) N +1 such that y i = (x i , a i ) for all 0 ≤ i ≤ N . Note that µ n (y n ) is the marginal probability mass function.

Consider µ, µ ∈ M µ0 the state-action distribution sequences induced by π, π respectively (i.e, µ = µ π and µ = µ π ). Thus, computing the relative entropy between the probability mass functions Where

N i=1 log P πi (y i |y i-1 ) P π i (y i |y i-1 ) = N i=1 log p i (x i |x i-1 , a i-1 )π i (a i |x i ) p i (x i |x i-1 , a i-1 )π i (a i |x i ) = N i=1 log π i (a i |x i ) π i (a i |x i ) .
Thus,

D(µ 1:N , µ 1:N ) = y µ 1:N ( y) N i=1 log π i (a i |x i ) π i (a i |x i ) = y µ 0 (y 0 )P π1 (y 1 |y 0 ) . . . P π N (y N |y N -1 ) N i=1 log π i (a i |x i ) π i (a i |x i ) = N i=1 x∈X a∈A µ i (x, a) log π i (a|x) π i (a|x) .
Where for the last equality we used that y0,...,yi-1 µ 0 (y 0 )P π1 (y 1 |y 0 ) . . . P πi (y i |y i-1 ) = yi µ i (y i ) and for a fixed y i , yi+1,...,y N P πi+1 (y i+1 |y i ) . . . P π N (y N |y N -1 ) = 1.

This proves the first equality of the lemma. We now prove the second. For this, we recall that Proposition A.1 gives a unique relation between a state-action distribution sequence µ ∈ M µ0 and the policy sequence π ∈ (∆ A ) X ×N inducing it by taking for all 1 ≤ i ≤ N , (x, a) ∈ X × A,

π i (a|x) = µ i (x, a) ρ i (x) ,
where ρ is the marginal on the states of µ. Using this relation, we have then that

D(µ 1:N , µ 1:N ) = N i=1 x∈X a∈A µ i (x, a) log π i (a|x) π i (a|x) = N i=1 x∈X a∈A µ i (x, a) log µ i (a|x) ρ i (x) ρ i (x) µ i (a|x) = N i=1 x∈X a∈A µ i (x, a) log µ i (a|x) µ i (a|x) - N i=1 x∈X a∈A µ i (x, a) log ρ i (x) ρ i (x) = N i=1 x∈X a∈A µ i (x, a) log µ i (a|x) µ i (a|x) - N i=1 x∈X ρ i (x) log ρ i (x) ρ i (x) = N i=1 D(µ i , µ i ) - N i=1 D(ρ i , ρ i )
which concludes the proof.

B.1 Proof of Theorem 4.1: formulation of Algorithm 2

Theorem. Let k ≥ 0. The solution of Problem (8) is µ k+1 = µ π k+1 , where for all n ∈ [N ], and (x, a) ∈ X × A,

π k+1 n (a|x) := π k n (a|x) exp τ k Qk n (x, a) a ∈A π k n (a |x) exp τ k Qk n (x, a )
, where Q is a regularized Q-function satisfying the following recursion

                 Qk N (x, a) = -∇f N (µ k N )(x, a) Qk n (x, a) = max πn+1∈(∆ A ) X -∇f n (µ k n )(x, a)+ x p n+1 (x |x, a) a π n+1 (a |x ) - 1 τ k log π n+1 (a |x ) π k n+1 (a |x ) + Qk n+1 (x , a ) .
Proof. At each iteration we seek to find µ k+1 a minimizer of min

µ π ∈Mµ 0 ∇F (µ k ), µ π + 1 τ k N n=1 E (x,a)∼µn(•) log π n (a|x) π k n (a|x) (19)
where recall that ∇F (µ k ), µ π := N n=1 ∇f n (µ k n ), µ π n . We further use that r n (x n , a n , µ n ) := -∇f n (µ n )(x n , a n ). Now, we use the optimality principle to solve this optimization problem with an algorithm backwards in time. Remember that the initial distribution µ 0 is always fixed. The equivalence between solving a minimization problem on sequences of state-action distributions in M µ0 and on sequences of policies in (∆ A ) X ×N (see Proposition A.1), allows us to reformulate Problem (19) on M µ0 into a problem on (∆ A ) X ×N , thus

(19) = max π∈(∆ A ) X ×N N n=0 x,a µ π n (x, a)r n (x, a, µ k n ) - 1 τ k N n=1 x,a µ π n-1 (x, a)
x ,a

p n (x |x, a)π n (a |x ) log π n (a |x ) π k n (a |x ) = max π∈(∆ A ) X ×N N n=0 x,a µ π n (x, a) r n (x, a, µ k n ) - 1 τ k x ,a p n+1 (x |x, a)π n+1 (a |x ) log π n+1 (a |x ) π k n+1 (a |x ) = max π∈(∆ A ) X ×N E π r N (x N , a N , µ k N ) + N -1 n=0 r n (x n , a n , µ k n ) - 1 τ k x ,a p n+1 (x |x n , a n )π n+1 (a |x ) log π n+1 (a |x ) π k n+1 (a |x )
.

Let us define a regularized version of the state-action value function that we denote by Qk , such that for all i ∈ [N ], (x, a) ∈ X × A,

Qk i (x, a) = max π i+1:N ∈(∆ A ) X ×(N -i) E π r N (x N , a N , µ k N ) + N -1 n=i r n (x n , a n , µ k n ) - 1 τ k x ,a p n+1 (x |x n , a n )π n+1 (a |x ) log π n+1 (a |x ) π k n+1 (a |x ) (x i , a i ) = (x, a) , (20)
where π i+1:N = {π i+1 , . . . , π N }.

First, note that E (x,a)∼µ0(•) [ Qk 0 (x, a)] = (19). Moreover, the optimality principle states that this regularized state-action value function satisfies the following recursion

               QN (x, a) = r N (x, a, µ k N ) Qi (x, a) = max πi+1∈(∆ A ) X r i (x, a, µ k i )+ x p i+1 (x |x, a) a π i+1 (a |x ) - 1 τ k log π i+1 (a |x ) π k i+1 (a |x ) + Qi+1 (x , a ) .
Thus, to solve (19) we compute backwards in time, i.e. for i = N -1, . . . , 0, for all x ∈ X ,

π k+1 i+1 (•|x) ∈ arg max π(•|x)∈∆ A π(•|x), Qk i+1 (x, •) - 1 τ k D π(•|x), π k i+1 (•|x) ,
where D is the KL divergence.

The solution of this optimisation problem for each time step i can be found by writing the associated Lagrangian function L. Let λ be the Lagrangian multiplier associated with the simplex constraint. For simplicity, let

π x := π(•|x), π k x := π k i+1 (•|x) and Qk x := Qk i+1 (x, •). Thus, L(π x , λ) = π x , Qk x - 1 τ k D(π x , π k x ) -λ a∈A π x (a) -1 .
Taking the gradient of the Lagrangian with respect to π x (a) for each a ∈ A gives

∂L(π x , λ) ∂π x (a) = Qk x (a) - 1 τ k log π x (a) π k x (a) - 1 τ k -λ,
and thus

∂L(π x , λ) ∂π x (a) = 0 =⇒ π x (a) = π k x (a) exp τ k Qk x (a) -1 -τ k λ .
Applying the simplex constraint, a∈A π x (a) = 1, we find the value of the Lagrangian multipler λ, and we get for all a ∈ A

π x (a) = π k x (a) exp τ k Qk x (a) a ∈A π k x (a ) exp τ k Qk x (a )
, which proves the theorem.

B.2 Proof of Proposition 4.3

Proposition. Let µ ∈ M µ0 with marginal given by ρ ∈ (∆ X ) N . The divergence Γ is a Bregman divergence induced by the function

ψ(µ) := N n=1 φ(µ n ) - N n=1 φ(ρ n ).
Also, ψ is 1-strongly convex with respect to the • ∞,1 norm.

Proof. Lemma B.1 states that for any µ ∈ M µ0 and µ ∈ M * µ0 , induced by π, π respectively as in Equation 4, with the same initial state-action distribution, i.e. µ 0 = µ 0 , we have

Γ(µ, µ ) := N n=1 E (x,a)∼µn(•) log π n (a |x ) π k n (a |x ) = N n=1 D(µ n , µ n ) - N n=1 D(ρ n , ρ n ).
Recall that φ is the negentropy and that D is the Bregman divergence induced by the negentropy. Define the function ψ

: (∆ X ×A ) N → R such that for any µ ∈ (∆ X ×A ) N ψ(µ) := N n=1 φ(µ n ) - N n=1 φ(ρ n ).
To show Γ is a Bregman divergence induced by ψ we need to show that for any µ, µ ∈ (∆ X ×A ) N ,

ψ(µ) -ψ(µ ) -∇ψ(µ ), µ -µ = Γ(µ, µ ).
For that, first recall that the marginal ρ is such that for each 1 ≤ n ≤ N , and for all x ∈ X , ρ n (x) = a∈A µ n (x, a). Thus,

ψ(µ) = n x,a µ n (x, a) log(µ n (x, a)) - x ρ n (x) log(ρ n (x)) = n x,a µ n (x, a) log µ n (x, a) a µ n (x, a ) . ( 21
) which implies that Γ(µ, µ ) ≥ 1 2 µ -µ 2 ∞,1 . (23)
Finally, plugging back into Equation ( 22) shows that ψ is 1-strongly convex with respect to the norm • ∞,1 .

B.3 Complements of the proof of Theorem 4.2 Lemma B.2. Let f n : ∆ X ×A → R be convex and -Lipschitz with respect to the norm

• 1 for all n ∈ [N ]. If F : (∆ X ×A ) N → R is defined for all µ := (µ n ) n∈[N ] ∈ (∆ X ×A ) N as F (µ) := N n=1 f n (µ n ), then F is also convex and L-Lipschitz with respect to the norm • ∞,1 for L = N .
Proof. Convexity: F is convex as the sum of convex functions. Proof. Let γ > 0. Recall that, for all n ∈ [N ], and for all (x, a) ∈ X × A, p n (x|x, a)

Lipschitz: Let µ, µ ∈ (∆ X ×A ) N . As f n is Lipschitz with respect to • 1 with constant , then |f n (µ n ) - f n (µ n )| ≤ µ n -µ n 1 for all 1 ≤ n ≤ N . Therefore, |F (µ) -F (µ )| = N n=1 f n (µ n ) -f n (µ n ) ≤ N n=1 |f n (µ n ) -f n (µ n )| ≤ N n=1 µ n -µ n 1 ≤ N µ -µ ∞,1 .

C Proofs of Subsection 5.1: concentration results

:= P g n (x, a, ε n ) = x and pt n (x|x, a) = 1 M t n M t n s=1 δ gn(x,a,ε s n )
where M t n is the number of times we observe step n until the start of episode t, and ε s n is the s-th noise observed at step n. Note that M t n is not random. Therefore,

p n -pt n (Λ)(x, a) := x ∈X p n (x |x, a) -pt n (x |x, a) Λ(x ) = E εn∼hn(•) Λ g n (x, a, ε n ) - 1 M t n M t n s=1 Λ g n (x, a, ε s n ) .
From the hypothesis on the bound of Λ, we have that almost surely Λ g n (x, a, ε s

i ) ∈ [- √ γ/2, √ γ/2] for all
s ∈ M t n , therefore, applying Hoeffding's inequality to the sequence of random variables Λ g n (x, a, ε s

i ) s∈[M t n ]
yields, for all ξ > 0,

P p n -pt n (Λ)(x, a) ≥ ξ ≤ exp -2ξ 2 M t n γ . ( 24
)
Applying the union bound we then get that simultaneously for all (x, a) ∈ X × A, steps n ∈ [N ] and episodes t ∈ [T ],

p n -pt n (Λ)(x, a) ≤ γ 2M t n log N |X ||A|T δ
holds with probability 1 -δ for any 0 < δ < 1.

where we define the function Λ

i,n,π v : X → R for any v ∈ R X ×A as Λ i,n,π v (x) := a∈A π i (a|x) y∈X ×A K i+1:n (y)v(y). (25) If v ∞ ≤ V , then for all x ∈ X , |Λ i,n,π v (x)| ≤ a∈A π i a|x y ∈X ×A K i+1:n (y )|v(y )| ≤ V a∈A π i a|x y ∈X ×A K i+1:n (y ) = V. Therefore, Λ i,n,π v ∞ ≤ V .
C.3 Proof of Proposition 5.5: upper bound on R M DP T Proposition. We consider an episodic MDP with finite state space X , finite action space A, episodes of length N , and probability kernel p

:= (p n ) n∈[N ] . We let F t := N n=1 f t n convex with f t n -Lipschitz with respect to the norm • 1 for all n ∈ [N ], t ∈ [T ]. Then, with probability 1 -δ, Greedy MD-CURL obtains, R M DP T (π t ) t∈[T ] ≤ N 2 2T M log N |X ||A|T δ .
The exact same result being also valid for R M DP T π * .

Proof. The proof steps are the same for both terms, hence we show only the steps for R M DP T (π t ) t∈ [T ] . Using the convexity of F t we obtain

R M DP T (π t ) t∈[T ] ≤ T t=1 ∇F t (µ π t ,p ), µ π t ,p -µ π t , pt = T t=1 N n=1 ∇f t n (µ π t ,p ), µ π t ,p n -µ π t , pt n .
To bound the inner product for each n, we first use the result of Lemma 5.2 to obtain that

∇f t n (µ π t ,p ), µ π t ,p n -µ π t , pt n = n i=1 y∈X ×A µ π, pt i-1 (y) p i -pt i Λ i,n,π t ∇f t n (µ π t ,p ) (y).
As f t n is -Lipschitz with respect to the norm • 1 for all n and t, then for all state-action distribution

µ n ∈ ∆ X ×A , ∇f t n (µ n ) ∞ := sup (x,a) |∇f t n (µ n )(x, a)| ≤ .
Hence, from the second result of Lemma 5.2 we have Λ i,n,π t ∇f t n (µ π t ,p ) ∞ ≤ . Therefore, all the conditions of Lemma 5.1 are satisfied with γ = 4 2 , meaning that

T t=1 N n=1 ∇f t n (µ n ), µ π t ,p n -µ π t , pt n = T t=1 N n=1 n-1 i=1 y∈X ×A µ π t , pt i-1 (y) p i -pt i Λ i,n,π t ∇f t n (µ π t ,p ) (y) ≤ T t=1 N 2 2 M t log N |X ||A|T δ ≤ N 2 2T M log N |X ||A|T δ
holds with probability 1 -δ, where we use that in Greedy MD-CURL,

M t n = M (t -1) for all n ∈ [N ].
Proof. For µ ∈ (∆ X ×A ) N and for Lagrangian multipliers λ n ∈ R associated to the constraints (x,a)∈X ×A µ n (x, a) = 1 for all n ∈ [N ], consider the Lagrangian given by

L(µ, λ) = ψ(µ) + n λ n 1 - x,a µ n (x, a) .
For every n ∈ [N ], and (x, a) ∈ X × A,

∂L(µ, λ) ∂µ n (x, a) = log µ n (x, a) a µ n (x, a ) -λ n = 0, thus µ n (x, a) a µ n (x, a ) = exp(λ n ).
To satisfy the constraint for each n, we need

x,a

µ n (x, a) = x,a exp (λ n ) a µ n (x, a ) = exp (λ n )|A| = 1.
Using the decomposition of ψ proved in Equation ( 21), we get

-ψ(µ) = n x,a µ n (x, a) log a µ n (x, a ) µ n (x, a) ≤ n x,a µ n (x, a) log(|A|) = N log(|A|).
D.3 Proof of Lemma 5.6

Lemma. For any policy sequence π, the estimation of the probability kernel for two consecutive episodes done by Greedy MD-CURL satisfies, for all episodes t ∈ [T -1], the following inequality

µ π, pt+1 -µ π, pt ∞,1 ≤ 2N t .
Proof. For all (x, a, x ) ∈ X × A × X , and for all i

∈ [N ], pt+1 i (•|x, a) -pt i (•|x, a) 1 = x ∈X |p t+1 i (x |x, a) -pt i (x |x, a)| = x ∈X 1 M t M j=1 δ gi(x,a,ε j,t i ) (x ) + M (t -1)p t i (x |x, a) -pt i (x |x, a) = 1 M t x ∈X M j=1 δ gi(x,a,ε j,t i ) (x ) -pt i (x |x, a) ≤ 2 t . (26)
Therefore, using the result of Lemma D.1 with pt i and pt+1 i ,

µ π, pt+1 -µ π, pt ∞,1 = sup n∈[N ] µ π, pt+1 n -µ π, pt n 1 ≤ sup n∈[N ] n-1 i=0 x,a µ π, pt i (x, a) pt+1 i (•|x, a) -pt i (•|x, a) 1 ≤ 2N t .
D.4 Auxiliary result: bound between distributions induced by π t and πt Lemma D.3. For all episodes t ∈ [T ], where π t is the strategy calculated using Greedy MD-CURL, πt = (1 -α t )π t + αt |A| , and pt , pt+1 are two consecutive estimates of the probability kernel by Greedy MD-CURL, we have

µ π t , pt -µ πt , pt+1 ∞,1 ≤ sup n∈[N ] n-1 i=1 x,a µ π t , pt i (x, a) pt i+1 (•|x, a) -pt+1 i+1 (•|x, a) 1 + 2nα t .
Proof. Using similar arguments as in Lemma D.1, we get that for all n ∈ [N ],

µ π t , pt n -µ πt , pt+1 n 1 = x,a µ π t , pt n (x, a) -µ πt , pt+1 n (x, a) ≤ x,a x ,a µ π t , pt n-1 (x , a )p t n (x|x , a )π t n (a|x) -µ πt , pt+1 n-1 (x , a )p t+1 n (x|x , a ) (1 -α t )π t n (a|x) + α t 1 |A| ≤ x,a x ,a µ π t , pt n-1 (x , a )p t n (x|x , a ) -µ πt , pt+1 n-1 (x , a )p t+1 n (x|x , a ) π t n (a|x) + α t x,a x ,a µ πt , pt+1 n-1 (x , a )p t+1 n (x|x , a ) π t n (a|x) - 1 |A| ≤ x x ,a µ π t , pt n-1 (x , a )p t n (x|x , a ) -µ π t , pt n-1 (x , a )p t+1 n (x|x , a ) + µ π t , pt n-1 (x , a )p t+1 n (x|x , a ) -µ πt , pt+1 n-1 (x , a )p t+1 n (x|x , a ) + 2α t ≤ x ,a µ π t , pt n-1 (x , a ) pt n (•|x , a ) -pt+1 n (•|x , a ) 1 + x ,a µ π t , pt n-1 (x , a ) -µ πt , pt+1 n-1 (x , a ) + 2α t ≤ x ,a µ π t , pt n-1 (x , a ) pt n (•|x , a ) -pt+1 n (•|x , a ) 1 + µ π t , pt n-1 -µ πt , pt+1 n-1 1 + 2α t ≤ n-1 i=0 x,a µ π t , pt i (x, a) pt i+1 (•|x, a) -pt+1 i+1 (•|x, a) 1 + 2nα t ,
where for the last inequality we use that µ π t , pt 0 = µ πt , pt+1 0

. To finish we just take the sup over n ∈ [N ].

D.5 Proof of Proposition 5.7: upper bound on R policy T Proposition. Consider an episodic MDP with finite state space X , finite action space A, episodes of length N , and probability kernel p :

= (p n ) n∈[N ] . Let F t := N n=1 f t n convex with f t n -Lipschitz with respect to the norm • 1 for all n ∈ [N ], t ∈ [T ]. Let b be defined as in Equation (14). Then, Greedy MD-CURL obtains, for τ = b L √ T , R policy T ≤ 2 N b √ T .
Proof. Using the convexity of F t ,

R policy T = T t=1 F t (µ π t , pt ) -F t (µ π * , pt+1 ) ≤ T t=1 l t , µ π t , pt -µ π * , pt+1
where l t := ∇F t (µ π t ,t ) to shorten notation, and we also use the notation introduced in the main paper µ t := µ π t , pt and μt := µ πt , pt , for all t ∈ [T ]. We begin by examining Problem (12):

µ t+1 ∈ arg min µ∈M t+1 µ 0 {τ l t , µ + Γ(µ, μt )}.
Since F t is a convex function and M t+1 µ0 is a convex set, the optimality conditions imply that for all ν t+1 ∈ M t+1 µ0 ,

τ l t + ∇ψ(µ t+1 ) -∇ψ(μ t ), ν t+1 -µ t+1 ≥ 0.
Recall that ψ is defined in Proposition 4.3 as the function inducing the Bregaman divergence Γ. Re-arranging the terms and using the three points inequality for Bregman divergences [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF] we get that,

τ l t , µ t+1 -ν t+1 ≤ ∇ψ(µ t+1 ) -∇ψ(μ t ), ν t+1 -µ t+1 = Γ(ν t+1 , μt ) -Γ(ν t+1 , µ t+1 ) -Γ(µ t+1 , μt ).
This is in particular valid for ν t+1 := µ π * , pt+1 . Therefore, by adding and subtracting τ l t , µ t on the left-hand side,

τ l t , µ t+1 -ν t+1 + τ l t , µ t -τ l t , µ t ≤ Γ(ν t+1 , μt ) -Γ(ν t+1 , µ t+1 ) -Γ(µ t+1 , μt ) ⇒ τ l t , µ t -ν t+1 ≤ τ l t , µ t -µ t+1 + Γ(ν t+1 , μt ) -Γ(ν t+1 , µ t+1 ) -Γ(µ t+1 , μt ).
Then, by summing over t ∈ [T ], and by taking ν t+1 := µ π * , pt+1 , we obtain

R policy T ≤ 1 τ T t=1 τ l t , µ t -µ t+1 -Γ(µ t+1 , μt ) A + 1 τ T t=1 Γ(ν t+1 , μt ) -Γ(ν t+1 , µ t+1 ) B . (27)
The term A appears due to our lack of knowledge of F t at the beginning of episode t for all episodes. To remedy this, we use Young's inequality and the strong convexity of Γ. Note that if we were to consider the case where all F t are known in advance, we would not have to deal with the A term. As for the term B, in the classic OMD proof [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] where the set of constraints is fixed the sum of the difference between the Bregman divergences telescopes (as we would with a fixed ν). However, since we are considering time-varying constraint sets, this does not happen in our case. We now proceed to find an upper bound for each term.

Step 1: upper bound on B We begin by analyzing the second term of the sum in Equation ( 27). Recall that ν t := µ π * , pt for all t ∈ [T ]. In order to make the Bregman divergence terms telescope we add and subtract Γ(ν t , µ t ) -Γ(ν t , μt ), obtaining

T t=1 Γ(ν t+1 , μt )-Γ(ν t+1 , µ t+1 ) = T t=1 Γ(ν t+1 , μt ) -Γ(ν t , μt ) (i) + T t=1 Γ(ν t , μt ) -Γ(ν t , µ t ) (ii) + T t=1 Γ(ν t , µ t ) -Γ(ν t+1 , µ t+1 ) (iii)
.

We now analyze each term. Using the definition of a Bregman divergence induced by ψ we get that

(i) = T t=1 ψ(ν t+1 ) -ψ(μ t ) -∇ψ(μ t ), ν t+1 -μt -ψ(ν t ) + ψ(μ t ) + ∇ψ(μ t ), ν t -μt = T t=1 ψ(ν t+1 ) -ψ(ν t ) + T t=1 ∇ψ(μ t ), ν t -ν t+1 ≤ -ψ(ν 1 ) + T t=1 ∇ψ(μ t ) 1,∞ ν t -ν t+1 ∞,1 ,
where in the last inequality we used that the first term telescopes and we apply Holder's inequality to the second term. Recall that for v :

= (v n ) n∈[N ] such that v n ∈ R X ×A , we defined v ∞,1 := sup n∈[N ] v n 1 . We now also define ζ 1,∞ := sup v {| ζ, v |, v ∞,1 ≤ 1} = sup n∈[N ]
ζ n 1 as the respective dual norm.

With our choice of Bregman divergence, and given the definition of π in Equation ( 13), for each n ∈ [N ], (x, a) ∈ X × A, |∇ψ(μ t )(n, x, a)| = | log(π t n (a|x))| ≤ log(|A|/α t ). Plugging this result with the result of Lemma 5.6 into the bound of (i) we obtain that

(i) ≤ -ψ(ν 1 ) + T t=1 N log |A| α t µ π * , pt -µ π * , pt+1 ∞,1 ≤ -ψ(ν 1 ) + 2N 2 T t=1 log |A| α t 1 t .
As for the second term, using our definition of Γ, we obtain that

(ii) = T t=1 n,x,a µ π * , pt n (x, a) log π * n (a|x) πt n (a|x) - n,x,a µ π * , pt n (x, a) log π * n (a|x) π t n (a|x) = T t=1 n,x,a µ π * , pt n (x, a) log π t n (a|x) πt n (a|x) = T t=1 n,x,a µ π * , pt n (x, a) log π t n (a|x) (1 -α t )π t n (a|x) + α/|A| ≤ N T t=1 (-log(1 -α t )) ≤ 2N T t=1 α t ,
where the last inequality is valid if 0 ≤ α t ≤ 0.5.

It is easy to see that the third term telescopes, therefore, as -Γ(ν T +1 , µ T +1 ) ≤ 0 as a Bregman divergence is always positive, (iii) ≤ Γ(ν 1 , µ 1 ).

Before adding back the three terms, note that, for µ 1 initialized such that ∇ψ(µ 1 ) = 0, we have Γ(ν 1 , µ 1 )-ψ(ν 1 ) = -ψ(µ 1 ). Furthermore, from Lemma D.2, -ψ(µ 1 ) ≤ N log(|A|). Therefore,

Γ(ν 1 , µ 1 ) -ψ(ν 1 ) ≤ N log(|A|). (28)
Summing over our bounds and using the Inequality (28), we get that B is upper bounded as

1 τ T t=1 Γ(ν t+1 , μt )-Γ(ν t+1 , µ t+1 ) ≤ 1 τ (i)+(ii)+(iii) ≤ N τ log(|A|)+ 2N 2 τ T t=1 log |A| α t 1 t + 2N τ T t=1 α t . ( 29
)
Step 2: Upper bound on A It remains to delimit the first term of the bound in R policy T in Equation ( 27) given by

A = 1 τ T t=1 τ l t , µ t -µ t+1 -Γ(µ t+1 , μt ) , (30)
representing what we pay for not knowing the loss function in advance. For that we use Young's inequality [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF].

Recall that Young's inequality states that for any σ > 0, for any dual norms,

a, b ≤ 1 2σ a 2 + σ 2 b 2 * .
Therefore, for any σ > 0 to be optimized later, and for each episode t ∈ [T ],

τ l t , µ t -µ t+1 -Γ(µ t+1 , μt ) ≤ τ 2 l t 2 1,∞ 2σ + σ 2 µ t -µ t+1 2 ∞,1 -Γ(µ t+1 , μt ), (31)
where recall that for v :

= (v n ) n∈[N ] such that v n ∈ R X ×A , we defined v ∞,1 := sup n∈[N ] v n 1 , and we let ζ 1,∞ := sup v {| ζ, v |, v ∞,1 ≤ 1} = sup n∈[N ]
ζ n 1 as the respective dual norm.

From Lemma B.1 and inequality (23) stating the strong convexity of ψ, we have that for all t ∈ [T ]

Γ(µ t+1 , μt ) = D(µ t+1 1:N , µ πt , pt+1 1:N ) ≥ 1 2 µ t+1 -µ πt , pt+1 2 ∞,1 (32)
where recall that µ 1:N is the joint state-action distribution while that µ := (µ n ) n∈ [N ] is the sequence of stateaction distributions.

Using that for any vectors a, b, c ∈ R d , and that for any norm • , a -b 2 ≤ 2 a -c 2 + b -c 2 , we then have by Equation ( 32)

1 4 µ t -µ t+1 2 ∞,1 -Γ(µ t+1 , μt ) ≤ 1 4 µ t -µ t+1 2 ∞,1 - 1 2 µ πt , pt+1 -µ t+1 2 ∞,1 ≤ 1 2 µ t -µ πt , pt+1 2 ∞,1 + µ πt , pt+1 -µ t+1 2 ∞,1 - 1 2 µ πt , pt+1 -µ t+1 2 ∞,1 = 1 2 µ t -µ πt , pt+1 2 ∞,1 . (33)
To bound µ t -µ πt , pt+1 2

∞,1 we first use Lemma D.3 which gives

µ t -µ πt , pt+1 ∞,1 ≤ N n=1 x,a µ t i (x, a) pt i+1 (•|x, a) -pt+1 i+1 (•|x, a) 1 + 2N α t .
Then, by Equation ( 26), pt

i+1 (•|x, a) -pt+1 i+1 (•|x, a) 1 ≤ 2/t for all t ∈ [T ], therefore µ t -µ πt , pt+1 2 ∞,1 ≤ 2N t + 2N α t 2 .
Therefore, plugging into Equation ( 31) with σ = 1/2 yields,

τ l t , µ t -µ t+1 -Γ(µ t+1 , μt ) ≤ τ 2 l t 2 1,∞ + 1 2 2N t + 2N α t 2 .
Summing over t ∈ [T ], and l t 1,∞ ≤ L := lN as showed in Lemma B.2 then entails:

A ≤ τ L 2 T + 1 2τ T t=1 2N t + 2N α t 2 . ( 34
)
Conclusion Finally, by replacing the final bounds of Equations ( 29) and (34), we obtain

R policy T ≤ A + B ≤ τ T L 2 + 2N 2 τ T t=1 1 t + α t 2 + N τ log(|A|) + 2N 2 τ T t=1 log |A| α t 1 t + 2N τ T t=1 α t . Let b := 2N 2 T t=1 1 t + α t 2 + T t=1 log |A| α t 1 t + 2N T t=1 α t + N log(|A|) 1 2 . Optimising over τ = b L √ T , R policy T ≤ 2Lb √ T = 2lN b √ T ,
concluding the proof.

In particular, if α t = 1 T for all t ∈ [T ], we have R policy T ≤ √ T log(T ).

E Bounds with unknown g

Now suppose that g n and h n in the model of Equation (3) are unknown. In this case, we have no information about the probability kernel, and the exploration/exploitation dilemma arises.

In order to learn the complete probability kernel, we need to modify the learning model slightly. Let us suppose that, at each episode t the learner maintains the number of visit counts to each episode (x, a) at time step n, we use a similar approach as in UC-O-REPS [START_REF] Rosenberg | Online convex optimization in adversarial Markov decision processes[END_REF]. Lemma E.2. For 0

< δ < 1, sup n∈[N ] T t=1 n-1 i=0 x,a µ π t ,p i (x, a) p i+1 (•|x, a) -pt i+1 (•|x, a) 1 ≤ ( √ 2 + 1)N |X | 4|A|T log T |X ||A|N δ + 2N |X | 2T log N δ
with probability 1 -2δ.

Proof. Using Lemma 19 from [START_REF] Jaksch | Nearoptimal regret bounds for reinforcement learning[END_REF], we have that

T t=1 1 {x t n =x,a t n =a} N t n (x, a) ≤ ( √ 2 + 1) N T n (x, a),
and by Jensen's inequality,

x,a T t=1

1 {x t n =x,a t n =a} N t n (x, a) ≤ ( √ 2 + 1) x,a |X ||A|T . (36)
Let (x t n , a t n ) n∈[N ] be the trajectory made by policy π t for all t ∈ [T ]. Therefore,

n-1 i=0 x,a µ π t ,p i (x, a) p i+1 (•|x, a) -pt i+1 (•|x, a) 1 (37) ≤ n-1 i=0 p i+1 (•|x t i , a t i ) -pt i+1 (•|x t i , a t i ) 1 + n-1 i=0 x,a µ π t ,p i (x, a) -1 {x t i =a,a t i =a} p i+1 (•|x, a) -pt i+1 (•|x, a) 1
By Lemma E.1, with probability at least 1 -δ, simultaneously for all i ∈ [N ] we have

T t=1 p i+1 (•|x t i , a t i ) -pt i+1 (•|x t i , a t i ) 1 ≤ T t=1 4|X | log T |X ||A|N δ max {1, N t i (x t i , a t i )} ≤ x,a T t=1 1 {x t i =x,a t i =a} 4|X | log T |X ||A|N δ max {1, N t i (x, a)} ≤ ( √ 2 + 1) 4|X | 2 |A|T log T |X ||A|N δ , (38)
where, for the last inequality, we use the result of Equation ( 36).

As for the second term, note that for all i ∈ [N ] and x ∈ X ,

a µ π t ,p i (x, a) -1 {x t i =x,a t i =a}
forms a martingale difference with respect to the trajectory (x s 0 , a s 0 , . . . , x s N , a s N ) s∈[T ] (the expectation of the term conditional on the past trajectory is zero). Therefore, by Azuma-Hoeffding inequality,

P T t=1 a µ π t ,p i (x, a) -1 {x t i =x,a t i =a} ≥ ε ≤ exp -2ε 2 4T .
Taking the union bound over i ∈ [N ], we get that with probability 1 -δ, simultaneously for all i ∈ [N ], and considering that p

i+1 (•|x, a) -p t i+1 (•|x, a) 1 ≤ 2, T t=1 x,a µ π t ,p i (x, a) -1 x t i =x,a t i =a p i+1 (•|x, a) -pt i+1 (•|x, a) 1 ≤ 2|X | 2T log N δ . (39)
Plugging the bounds on Equation ( 38) and (39) into Equation (37), we get that with probability 1 -2δ,

sup n∈[N ] T t=1 n-1 i=0 x,a µ π t ,p i p i+1 (•|x, a) -pt i+1 (•|x, a) 1 ≤ sup n∈[N ] n-1 i=0 ( √ 2 + 1) 4|X | 2 |A|T log T |X ||A|N δ + 2|X | 2T log N δ ≤ ( √ 2 + 1)N |X | 4|A|T log T |X ||A|N δ + 2N |X | 2T log N δ .
The result of Lemma E.2 allows us to state the following proposition bounding the term R M DP T (π t ) t∈[T ] :

Proposition E.3. We consider an episodic MDP with finite state space X , finite action space A, episodes of length N , and probability kernel p :

= (p n ) n∈[N ] . We let F t := N n=1 f t n convex with f t n -Lipschitz with respect to the norm • 1 for all n ∈ [N ], t ∈ [T ].
We consider the probability estimation per iteration as in Equation (35). Then, with probability 1 -δ, Greedy MD-CURL obtains,

R M DP T (π t ) t∈[T ] ≤ ( √ 2 + 1) N 2 |X | 4|A|T log T |X ||A|N δ + 2 N 2 |X | 2T log N δ .
Proof. Recall that, given the convexity of F t and by applying Holder's inequality using that if f t n are -Lipschitz with respect to • 1 then F is L-Lipschitz with respect to • ∞,1 for L = N (see Lemma B.2), we obtain that

R M DP T (π t ) t∈[T ] ≤ T t=1 ∇F t (µ π t ,p ), µ π t ,p -µ π t , pt ≤ T t=1 ∇F t (µ π t ,p ) * sup n∈[N ] µ π t ,p n -µ π t , pt n 1 ≤ L sup n∈[N ] T t=1 µ π t ,p n -µ π t , pt n 1 .
The result then follows from the application of Lemma D.1 and Lemma E.2.

To complete the bound on the regret R T , we need to bound R M DP T π * . For this, we need Lemma E.4, which states that the Greedy MD-CURL algorithm always computes policies that are lower bounded if

t n (x, a)(µ n ) ∈ [0, 1] for all (x, a) ∈ X × A, all µ n ∈ ∆ X ×A , n ∈ [N ] and t ∈ [T ]
. Proposition E.5 states the bound for R M DP T π * . Lemma E.4. Let (π t ) t∈[T ] be the sequence of policies obtained after computing T episodes of Greedy MD-CURL with α t ∈ (0, 1/2) and objective functions

F t = N n=1 f t n such that -∇f t n (µ n )(x, a) ∈ [0, 1].
Consequently, there is ξ ∈ (0, 1) such that for all (x, a) ∈ X × A, for all n ∈ [N ], and for all episodes t ∈ [T ], π t n (a|x) ≥ ξ.

Proof. At each episode t, we compute π t+1 := MD-CURL(1, πt \π t , F t , pt+1 , µ 0 , τ ), where πt = (1-α t )π t +α t 1 |A| , and the other parameters are defined in Algorithm 3.

From its definition, we can see that πt

ξ := min t∈[T ],n∈[N ] αt |A| exp(τ (N -n)) = 1 |A| exp(τ N ) min t∈[T ]
α t , we then have for all (x, a) ∈ X × A, for all n ∈ [N ], and for all episodes t ∈ [T ], π t n (a|x) ≥ ξ. Proposition E.5. We consider an episodic MDP with finite state space X , finite action space A, episodes of length N , and probability kernel p := (p n ) n∈ [N ] . We let F t := N n=1 f t n convex with f t n -Lipschitz with respect to the norm • 1 for all n ∈ [N ], t ∈ [T ]. We let ξ be the lower bound of π t n (a|x) for all n, t, (x, a) defined as in Lemma E.4. We consider the probability estimation per iteration as in Equation (35). Then, with probability 1 -2δ, Greedy MD-CURL obtains,

R M DP T π * ≤ 1 ξ N ( √ 2 + 1) N 2 |X | 4|A|T log T |X ||A|N δ + 2 N 2 |X | 2T log N δ .
Proof. Recall that, given the convexity of F t and by applying Holder's inequality using that if f t n are -Lipschitz with respect to • 1 then F is L-Lipschitz with respect to • ∞,1 for L = N (see Lemma B.2), we obtain that Here, we show regret in terms of the number of episodes T and do not worry about other constant terms. We use to denote an inequality up to constant or logarithmic terms independent of T . To simplify, we take α t = α for all t ∈ [T ]. Therefore, α and τ are the parameters to be optimized. We hypothesize that α < 1, T α ≥ log 1 α log(T ), and τ ≤ 1 N . We will later verify when the optimized α and τ satisfy these conditions. From Proposition E.3, we have R M DP T (π t ) t∈[T ] T log(T ).

From Proposition 5.7,

R policy T τ T + T τ α 2 + 1 τ log 1 α log(T ) + T τ α τ T + T τ α.
From Proposition E.5, we have If T > 1, then the conditions α < 1 and T α ≥ log 1 α log(T ) are satisfied. For T ≥ N 4N +2 , then τ ≤ 1/N . In a classic non-episodic online learning scenario, or in an episodic MDP with stationary probability kernels, we would not incur the term on ξ N but only ξ. This would reduce the final regret bound to O T 5 6 for any T ≥ 1. That is for example the case of the showcase experiments in Section 6 and Appendix F.

F Additional experiments

F.1 MD-CURL known probability kernel

We present the state distribution induced by the policies computed with MD-CURL in the offline optimization scenario when both g n and h n are known for varying steps n and iterations k. The episode length is fixed to N = 100 for all experiments. We illustrate the Entropy Maximization problem in Figure 6 and the Multi-Objective problem in Figure 7, and show that MD-CURL achieves the main goal in both cases.

F.2 Greedy MD-CURL with completely unknown probability kernel

In this section, we present the state distribution induced by the policies computed with Greedy MD-CURL in the online learning scenario. We assume that both g n and h n are unknown, and we estimate the probability kernel pt using Equation ( 35) at each episode. We vary the steps n and episodes t, and fix the episode length to N = 100 for all experiments.

We illustrate the Entropy Maximization problem in Figure 8 and the Multi-Objective problem in Figure 9 with a central noise of a probability of 0.2. These results show that even when the full dynamics are unknown, Greedy MD-CURL can still achieve the main goal.

  5.3.1 Bounding R M DP T Here we show the bounds on R M DP T (π t ) t∈[T ] and R M DP T (π * ). Both indicate the difference between the loss of playing a sequence of policies over T episodes in the actual MDP and the loss of playing the same sequence of policies but in the estimated MDP. For the first term, the sequence is that produced by Greedy MD-CURL, i.e. (π t ) t∈[T ] , and for the second term, it is the best stationary policy over the horizon T , i.e. π * . The results are presented in Proposition 5.5 and use the lemmas from Subsection 5.1. Proposition 5.5. Under the same hypothesis as in Theorem 5.4, with probability 1-δ, Greedy MD-CURL obtains,

Figure 1 :

 1 Figure 1: [left] Initial agent distribution; [middle] Distribution induced by the uniform policy; [right] The three targets.

Figure 2 :Figure 3 :

 23 Figure 2: Entropy maximisation: [left] MD-CURL distribution at N = 40; [right] Log regret.

Figure 4 :Figure 5 :

 45 Figure 4: Log regret per iteration, N = 40: [left] Entropy maximisation; [right] Multi-objectives.

  N ( y) log µ 0 (y 0 )P π1 (y 1 |y 0 ) . . . P π N (y N |y N -1 ) µ 0 (y 0 )P π 1 (y 1 |y 0 ) . . . P π N (y N |y N -1 ) = y0,...,y N µ 1:N ( y) N i=1 log P πi (y i |y i-1 ) P π i (y i |y i-1 ) .

C. 1

 1 Proof of Lemma 5.1 Lemma. Let γ > 0. For any 0 < δ < 1, and for any function Λ : X → R such that |Λ(x )| ≤ √ γ/2 for all x ∈ X , p n -pt n Λ (x, a) 1 -δ simultaneously for all (x, a) ∈ X × A, steps n ∈ [N ], and episodes t ∈ [T ].

  n (a|x) ≥ αt |A| . The closed form solution of one iteration of MD-CURL with the given parameters gives π t+1 n (a|x) = πt n (a|x) exp τ Qt n (x, a) a ∈A πt n (a |x) exp τ Qt n (x, a ) , where Qt n (x, a) is defined in Equation (10) with -∇f t n (x, a)(µ t n ) and πt at the place of π k . As -∇f t n (x, a)(µ t n ) ∈ [0, 1], we have 1 ≤ exp τ Qt n (x, a ) ≤ exp(τ (N -n)). Therefore, we have π t+1 n (a|x) ≥ αt |A| exp(τ (N -n)) for all steps n ∈ [N ] and (x, a).

Taking

  µ π * , pt ), µ π * , pt -µ π * ,p ≤ T t=1 ∇F t (µ π t ,p ) * sup n∈[N ] µ π * , pt n -µ π * ,) ≥ ξ for all n ∈ [N ], t ∈ [T ]and (x, a) ∈ X × A, we get n . This can be demonstrated recursively: suppose it's true for n, then for n + 1, by definitionµ π t ,p n+1 (x, a) = x ,a µ π t ,p n (x , a )p n+1 (x|x , a )π t n+1 (a|x) ≤ x ,a ξ n µ π * ,p n (x,a )p n+1 (x|x , a )π * n+1 (a|x)ξ = µ π * ,p n+1 (x, a)ξ n+1 . a) p i+1 (•|x, a) -p t i+1 (•|x, a) a) p i+1 (•|x, a) -p t i+1 (•|x, a) inequality is obtained by following the same steps of the proof from Lemma E.2. Conclusion: bounding R T We join the propositions E.3 and E.5 bounding R M DP T (π t ) t∈[T ] and R M DP T π * when playing Greedy MD-CURL with g n and h n unknown, and Proposition 5.7 bounding R policy T which remains general regardless of prior knowledge of g n and h n .

R

  T = R M DP T (π t ) t∈[T ] + R policy T + R M DP T π * τ T + T τ α + α -N T log(T ).We first optimize over τ . For τ = α α -N T log(T ).Then, we optimize over α. For α = T -

  (a) n = 10, k = 10 (b) n = 40, k = 10 (c) n = 100, k = 10 (d) n = 10, k = 50 (e) n = 40, k = 50 (f) n = 100, k = 50 (g) n = 10, k = 500 (h) n = 40, k = 500 (i) n = 100, k = 500

Figure 6 :

 6 Figure 6: State distribution of MD-CURL applied to Entropy Maximisation for steps n ∈ {10, 40, 100} and iterations k ∈ {10, 50, 500}.

  (a) n = 10, k = 10 (b) n = 40, k = 10 (c) n = 100, k = 10 (d) n = 10, k = 50 (e) n = 40, k = 50 (f) n = 100, k = 50 (g) n = 10, k = 500 (h) n = 40, k = 500 (i) n = 100, k = 500

Figure 7 :

 7 Figure 7: State distribution of MD-CURL applied to Multi-Objectives for steps n ∈ {10, 40, 100} and iterations k ∈ {10, 50, 500}.

Figure 8 :

 8 Figure 8: State distribution of Greedy MD-CURL applied to Entropy Maximisation for steps n ∈ {10, 40, 100} and episodes t ∈ {10, 50, 500}.

Figure 9 :

 9 Figure 9: State distribution of Greedy MD-CURL applied to Multi-Objectives for steps n ∈ {10, 40, 100} and episodes t ∈ {10, 50, 500}.

  At time step n, an agent in state x n choosing action a n transitions to state x n+1 with probability p n+1 (x n+1 |x n , a n ). At the start of an episode, the agent's first state-action couple follows a fixed distribution µ 0 ∈ ∆ X ×A . Actions are chosen by means of a policy π

n : X → ∆ A at each time step. In an episode, when an agent follows a sequence of strategies

  Séguret, A., Wan, C., and Alasseur, C. (2021). A mean field control approach for smart charging with aggregate power demand constraints. In 2021 IEEE PES Innovative Smart Grid Technologies Europe (ISGT Europe), pages 01-05.

	Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C.,
	and Wang, M. (2020). Variational policy gradient
	method for reinforcement learning with general util-
	ities. In Larochelle, H., Ranzato, M., Hadsell, R.,
	Balcan, M., and Lin, H., editors, Advances in Neural
	Information Processing Systems, volume 33, pages
	4572-4583.
	Zimin, A. and Neu, G. (2013). Online learning in
	episodic markovian decision processes by relative en-
	tropy policy search. In Advances in Neural Infor-
	mation Processing Systems, volume 26, pages 1583-
	1591.

Computing the first order partial derivative of ψ with respect to µ n (x, a) for any (x, a) ∈ X × A and 1 ≤ n ≤ N , we get Hence, as φ(µ n ) = µ n , log(µ n ) and φ(ρ n ) = ρ n , log(ρ n ) , and

Now we just need to show that ψ is strongly convex. For that, we apply the following convexity property [START_REF] Boyd | Convex Optimization[END_REF]:

where (a) comes from the definition of the KL divergence D and (b) comes from the definition of Γ.

It remains to find a norm that lower bound the right-hand side. By Lemma B.1,

the last inequality being a consequence of Pinsker's inequality. The norm • TV stands for the total variation norm. Let y represent an element of (X × A) N +1 such that y i ∈ X × A for all 0 ≤ i ≤ N . Observe that

Thus,

C.2 Proof of Lemma 5.2 Lemma. For any vector v ∈ R |X |×|A| , for any strategy π and for all n ∈

where

Proof. For y ∈ X × A, we denote by v(y) the element y of vector v.

For all n ∈ [N ], for all y := (x, a) ∈ X × A and y := (x , a ) ∈ X × A, let

For η a vector over X × A, we define for all y ∈ X × A and y 0 ∈ X × A the following notations

We can then rewrite the definition of a state-action distribution satisfying the Markovian dynamics and induced by a policy π stated in Equation ( 4) as µ π,p n = µ 0 K 1:n , and µ π, pt n = µ 0 Kt 1:n . With the convention that K n+1:n := Id is the identity operator for all n, then

Note that, for all y ∈ X × A, and all i ∈ {0, . . . , n},

D Proofs of Theorem 5.4: upper bound on R T D.1 Auxiliary result: L 1 bound between distributions induced by the same policy but different probability kernels

The bound of Theorem 5.4 depends on the auxiliary lemma bellow stating that the L 1 deviation of two stateaction distributions induced by the same policies but different probability kernels is bounded by the L 1 difference between the probability kernels. Lemma D.1. For any strategy π ∈ (∆ A ) X ×N , for any two probability kernels p = (p n ) n∈[N ] and q = (q n ) n∈ [N ] such that p n , q n : X × A × X → [0, 1], and for all n ∈ [N ],

Proof. From the definition of a state-action distribution sequence induced by a policy π in a probability kernel p in Equation ( 4), we have that for all (x, a) ∈ X × A and n ∈ [N ],

Thus,

Since for n = 0, µ π,p 0 -µ π,q 0 1 = 0, by induction we get that

denoted N t n (x, a), and the number of times this event is followed by a transition to a state x , denoted M t n (x |x, a), that is

To ease notations, we take M = 1 in this section. We define pt , at each (x, a Recall that the regret R T is decomposed as R T := R M DP