Aymen Al-Marjani

Andrea Tirinzoni

Emilie Kaufmann

Towards Instance-Optimality in Online PAC Reinforcement Learning

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

Introduction

We consider the online Probably Approximately Correct Reinforcement Learning (PAC RL) problem, in which an agent sequentially interacts with an environment modeled as a Markov Decision Process (MDP), with the goal of learning a near-optimal policy as quickly as possible. More precisely, given a precision ε ≥ 0 and a risk parameter δ ∈ (0, 1), the agent is required to return a policy π whose value is within ε of the value of the optimal policy, with probability at least 1 -δ. The agent's performance is evaluated through its sample complexity, defined as the number of interactions with the environment needed to output such a policy π.

Since its introduction by [START_REF] Fiechter | Efficient reinforcement learning[END_REF], this problem has been extensively investigated from a minimax point of view in two different settings: discounted MDPs (Azar et al., 2013;[START_REF] Sidford | Near-optimal time and sample complexities for solving markov decision processes with a generative model[END_REF][START_REF] Agarwal | Model-based reinforcement learning with a generative model is minimax optimal[END_REF], in which the value of a policy is the expected (infinite) sum of rewards discounted by a factor γ ∈ (0, 1), and finite-horizon (or episodic) MDPs [START_REF] Dann | Sample complexity of episodic fixed-horizon reinforcement learning[END_REF][START_REF] Dann | Policy certificates: Towards accountable reinforcement learning[END_REF][START_REF] Kaufmann | Adaptive reward-free exploration[END_REF][START_REF] Ménard | Fast active learning for pure exploration in reinforcement learning[END_REF], in which the value is the expected sum of rewards up to a given horizon H. Notably, in the finite-horizon setting with S states, A actions, and horizon H, [START_REF] Dann | Sample complexity of episodic fixed-horizon reinforcement learning[END_REF] proved that any PAC RL agent must play at least Ω(SAH 2 log(1/δ)/ε 2 ) episodes to identify an ε-optimal policy in the worst-case. Their lower bound was derived under the assumption of time-homogeneous rewards and transitions, while a lower bound of Ω(SAH 3 log(1/δ)/ε 2 ) episodes was later derived by Domingues et al. (2021) for the time-inhomogeneous case. There exist algorithms with sample complexity matching these lower bounds [START_REF] Dann | Policy certificates: Towards accountable reinforcement learning[END_REF][START_REF] Ménard | Fast active learning for pure exploration in reinforcement learning[END_REF].

Unfortunately, minimax optimality is not informative about the performance of an algorithm under different MDPs of the same size (H, S, A). For instance, let us imagine a first MDP with deterministic transitions and a tree structure which has a single optimal trajectory whose rewards are all considerably 1 higher than the rewards in any other trajectory. Let us also consider a second MDP in which all actions yield exactly the same reward, but this information is unknown to the agent beforehand. One would naturally expect the PAC RL task to be much easier in the first MDP where a few episodes should suffice to detect that the policy following the good trajectory is optimal. In the second one, however, no reasonable algorithm can confidently state that a policy is ε-optimal before having estimated uniformly well (with ε-precision) the value of all other policies. This motivates a recent line of works focused on designing adaptive algorithms with instance-dependent guarantees, i.e., sample complexity bounds featuring some characteristics of the underlying MDP that go beyond its size as in minimax results. These characteristics have been expressed with different notions of sub-optimality gaps. The first algorithm of this kind is BESPOKE [START_REF] Zanette | Almost horizon-free structure-aware best policy identification with a generative model[END_REF], which was proposed for discounted MDPs. Its gap-based sample complexity is shown to be never worse than the minimax rate, while it can be significantly smaller in some MDPs. [START_REF] Taupin | Best policy identification in linear mdps[END_REF] later proposed GSS, a PAC RL algorithm for discounted linear MDPs [START_REF] Jin | Provably efficient reinforcement learning with linear function approximation[END_REF] along with GSS-E, its counterpart for episodic linear MDPs. The problem of exact identification of the optimal policy (ε = 0) and the more complex identification of a Blackwell-optimal policy were treated by Marjani and Proutiere (2021) and [START_REF] Boone | Identification of blackwell optimal policies for deterministic MDPs[END_REF], respectively. All these works assume that a generative model is available, i.e., that the learner can query a transition from any state at any time. In the more challenging setting where interaction is allowed only through trajectories, Al Marjani et al. (2021) studied exact best-policy identification in discounted MDPs, while a more recent line of works has considered approximate identification (ε ≥ 0) in episodic MDPs (Wagenmaker et al., 2022a;[START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF]Wagenmaker and Jamieson, 2022;[START_REF] Tirinzoni | Optimistic PAC reinforcement learning: the instance-dependent view[END_REF][START_REF] Al-Marjani | Active coverage for pac reinforcement learning[END_REF]. All the proposed algorithms have sample complexity upper bounds of the form O C(M, ε) log(1/δ) , where C quantifies the hardness of learning an ε-optimal policy in the MDP M, δ is the risk, while O hides numerical constants and logarithmic factors of the relevant parameters. The expression of C is different for each algorithm but always dependent on some sub-optimality gaps (either values gaps or policy gaps, see Section 2 for a formal definition) and on state-visitation probabilities. We review these bounds in Section 4.

However, the lack of a general instance-dependent lower bound makes it difficult to assess the optimality of these approaches, i.e., how tight a complexity C(M, ε) is compared to the best possible rate. Indeed, the only instance-dependent lower bounds for PAC RL without a generative model are either restricted to MDPs with deterministic transitions [START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF] or cover only the case of exact best-policy identification (ε = 0) under the assumption that the optimal policy is unique [START_REF] Al | Adaptive sampling for best policy identification in markov decision processes[END_REF]. In this work, we fill this gap by answering the following question:

What is the best rate in log(1/δ) that a PAC RL algorithm can achieve on an episodic tabular MDP?

Contributions We derive the first instance-dependent lower bound for PAC RL that holds for any ε ≥ 0 and any tabular MDP (Theorem 1). As for bandit identification problems with many correct answers [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF], our lower bound holds when δ → 0. Beyond the asymptotic regime, we strengthen this result with an additional lower bound that holds for all δ > 0 in the special case of ε = 0 under the assumption that optimal policies share a unique state-action distribution (Theorem 2). Then, in Section 4, we review the complexity measures featured in existing upper bounds and show that the PEDEL algorithm of Wagenmaker and Jamieson (2022) matches our lower bound in tabular MDPs up to multiplicative H factors and an additive O(1/ε 2 ) term (Proposition 1). A shortcoming of PEDEL is that it is not computationally efficient as it explicitly enumerates all policies. We thus formulate an open question as to whether our bound can be attained by a computationally-efficient algorithm.

Preliminaries

We consider tabular finite-horizon Markov decision processes (MDPs). Formally, an MDP is a tuple

M := (S, A, H, {p h } h∈[H] , {ν h } h∈[H] , s 1 )
, where S is a finite set of S states, A is a finite set of A actions, H is the horizon, p h : S × A → P(S) and ν h : S × A → P(R)1 respectively denote the transition kernel and the reward distribution at stage h ∈ [H], while s 1 ∈ S is the initial state2 . A learner interacts with M through episodes of length H. At the beginning of each episode, the learner starts in the initial state s 1 . Then, for each stage h ∈ [H], the learner plays an action a h ∈ A and observes a stochastic transition to a new state s h+1 ∼ p h (s h , a h ) as well as a reward R h ∼ ν h (s h , a h ). The actions are usually chosen according to a Markovian (possibly stochastic) policy π = {π h } h∈[H] , i.e., a sequence of mappings π h : S → P(A), where π h (a|s) denotes the probability that the learner takes action a in state s at stage h. We denote by Π S (resp. Π D ) the set of all Markovian stochastic (resp. deterministic) policies.

Policy gaps, value gaps, and state-action distributions

Denoting by P π (resp. E π ) the probability (resp. expectation) operator induced by the execution of a policy π ∈ Π S for an episode on M, we let V π 1 := E π H h=1 R h s 1 be the value of π at the initial state3 . The policy gap of π is then defined as

∆(π) := V 1 -V π 1 , where V 1 := max π∈Π D V π 1 is the optimal value at s 1 . We use Q π h (s, a) := E π H =h R s h = s, a h = a and Q h (s, a) := max π∈Π D Q π h (s, a)
to denote the action-value function of π and the optimal value function, respectively. The value gap of the triplet (h, s, a) is then defined as

∆ h (s, a) := max b∈A Q h (s, b) -Q h (s, a) .
Moreover, we denote the visitation probability of (h, s, a) under π as p π h (s, a) := P π (s h = s, a h = a) and p π h (s) := P π (s h = s). We let Ω := p π h (s, a) h,s,a : π ∈ Π S } denote the set of all valid state-action distributions. It is well known (e.g., [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] that Ω is a polytope defined by the linear constraints ∀ρ ∈ Ω, ρ h (s, a) ≥ 0 ∀(h, s, a),

a∈A ρ 1 (s 1 , a) = 1, a∈A ρ 1 (s, a) = 0 ∀s = s 1 , a∈A ρ h (s, a) = s ,a ρ h-1 (s , a )p h-1 (s|s , a ) ∀(s, h) ∈ S × [|2, H|].

Learning problem

The learner interacts with an MDP M with unknown transition probabilities and reward distributions. Given a risk parameter δ ∈ (0, 1) and a precision ε ≥ 0 as input, the goal is to return a policy π ∈ Π D with the guarantee that P M (∆( π) ≤ ε) ≥ 1 -δ. To satisfy this requirement, the learner needs to gather samples from the transition and reward distributions of M by playing episodes in a sequential fashion. In each episode t ∈ N * , the learner selects a policy π t (based on past observations) and collects a new trajectory H t := {(s t h , a t h , R t h )} h∈ [H] under this policy, where a t h ∼ π t (s t h ). We let F t := σ((H u ) 1≤u≤t ) denote the sigma-algebra generated by trajectories up to episode t. The learner's performance is then evaluated by its sample complexity τ , which is a stopping time w.r.t, the filtration (F t ) t≥1 counting the (random) number of exploration episodes before termination.

Definition 1 ((ε, δ)-PAC algorithm). Let M be a set of MDPs. An algorithm is (ε, δ)-PAC on M if for all MDPs M ∈ M, with probability at least 1 -δ, it stops after playing τ < ∞ episodes on M and returns a deterministic policy π ∈ Π D satisfying ∆( π) ≤ ε.

Lower Bounds

We consider the class M 1 of stochastic MDPs with Gaussian rewards of unit variance4 , in which ν h (s, a) = N (r h (s, a), 1). While existing upper bounds commonly work under the stronger assumption that rewards lie in [0, 1] almost surely, we focus on this alternative setting since it has enabled the derivation of closed-form lower bounds that scale with intuitive quantities such as policy gaps [START_REF] Dann | Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning[END_REF][START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF]. Moreover, the complexity of an MDP is mostly characterized by the expected rewards r h (s, a) rather than the full distributions ν h (s, a), so that matching a lower bound for Gaussians while observing bounded rewards with the same mean is still very informative about the algorithm's adaptivity to the underlying problem.

General lower bound for approximate identification

Our first result is a general bound that holds for any ε ≥ 0 in the asymptotic regime δ → 0. We use the notation

Π ε := {π ∈ Π D : V π 1 (s 1 ) ≥ V 1 (s 1
) -ε} for the set of all deterministic ε-optimal policies.

Theorem 1. Any PAC RL algorithm that is (ε, δ)-PAC on M 1 satisfies, for any

M ∈ M 1 , lim inf δ→0 E M [τ ] log(1/δ) ≥ C LB (M, ε)
where

C LB (M, ε) := 2 min π ε ∈Π ε min ρ∈Ω max π∈Π D s,a,h p π h (s, a) -p π ε h (s, a) 2 ρ h (s, a)(∆(π) -∆(π ε ) + ε) 2 .
Theorem 1 states that no matter how adaptive a PAC RL algorithm is, there is a minimal cost in terms of episodes that it must pay in order to learn an ε-optimal policy of M. This cost is instance-dependent since it is a functional of M, the MDP to be learned. The proof of Theorem 1 is deferred to Appendix A. It follows similar steps as the proof of the lower bound for ε-best arm identification (and other pure exploration problems) of [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF].

Finite-δ bound for exact identification

In the case of exact identification (i.e. ε = 0), we further derive a lower bound which is valid for any δ ∈ (0, 1) under the assumption that the optimal state-action distribution is unique. In particular, we assume that there exists p ∈ Ω s.t. for any optimal policy π (i.e., with

V π 1 = V 1 )
we have p π = p . Note that this is a generalization of the assumption of "unique optimal trajectory" from [START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF], under which we know that exact identification to be possible with a sample complexity that does not scale with ε. It is also the same assumption considered in [START_REF] Tirinzoni | A fully problem-dependent regret lower bound for finite-horizon mdps[END_REF]. As shown in that paper, it implies that there is a unique optimal action in states visited with positive probability by some optimal policy, but there can be arbitrary many optimal actions in all other states.5

Theorem 2. Fix any MDP M ∈ M 1 s.t. the optimal state-action distribution p is unique. Then, for any PAC RL algorithm that is (0, δ)-PAC on M 1 ,

E M [τ ] ≥ 2 min ρ∈Ω max π∈Π D :∆(π)>0 s,a,h (p π h (s, a) -p h (s, a)) 2 ρ h (s, a)∆(π) 2 log 1 2.4δ
.

Remark 1. When S = H = 1, this bound exactly coincides with the lower bound for best-arm identification in Gaussian multi-armed bandits [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF].

Proof. The idea of the proof is to explicitly compute the smallest KL divergence between the distribution of the observations under the MDP M and under any alternative M that has the same transitions but a different mean reward function r h . Within the class M 1 , the KL divergence of observations between M and M takes the simple form

KL(P M , P M ) = h,s,a E M [n τ h (s, a)] r h (s, a) -r h (s, a) 2 2 .
Note that, since p is unique, any (0, δ)-PAC algorithm satisfies

P M (V π 1 = V 1 ) = P M (p π = p ) ≥ 1 -δ. Now fix a sub-optimal policy π for M (i.e., with ∆(π) > 0). Note that V π 1 = r T p π < V 1 = r T p .
We look for the closest alternative M such that r T p π > r T p , i.e., where π becomes better than any optimal policy of M. This can be computed by the quadratic program

min r: r T p π > r T p s,a,h E[n τ h (s, a)] (r h (s, a) -r h (s, a)) 2 2 = ∆(π) 2 2 s,a,h (p π h (s,a)-p h (s,a)) 2 E[n τ h (s,a)]
.

By the (0, δ)-PAC property, in such closest alternative we have P M (p π = p ) ≤ δ. Then, Lemma 1 of [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF] ensures that KL(P M , P M ) ≥ log 1 2.4δ . Thus, for any π with ∆(π) > 0,

1 ≥ 2 s,a,h (p π h (s, a) -p h (s, a)) 2 E[n τ h (s, a)]∆(π) 2 log 1 2.4δ
.

Multiplying both sides by E[τ ] and maximizing over sub-optimal policies, we obtain

E[τ ] ≥ 2 max π∈Π D :∆(π)>0 s,a,h E[τ ] E[n τ h (s, a)] (p π h (s, a) -p h (s, a)) 2 ∆(π) 2 log 1 2.4δ
.

Now it is easy to see that ρ h (s, a) := E[n τ h (s, a)]/E[τ ]
is a valid state-action distribution (i.e., ρ ∈ Ω). Thus, minimizing the right-hand side over all ρ ∈ Ω concludes the proof.

Interpreting the lower bound

While the expression of the lower bound might seem mysterious at a first glance, we provide an interpretation in terms of confidence intervals for the simpler setting of known transitions and unknown rewards. Our explanation hinges on the following concentration inequality, proved in Appendix B.

Lemma 1. Assume the reward distribution ν h (s, a) to be 1-subgaussian6 with mean r h (s, a) for all (h, s, a). For any policy π ∈ Π D , define the estimator V π,t

1 := h,s,a p π h (s, a) r t h (s, a)
, where r t h (s, a) is the MLE of r h (s, a) using samples gathered until episode t. We have that

P ∀t ≥ t 0 , ∀π, π ∈ Π D , ( V π,t 1 -V π ,t 1 ) -(V π 1 -V π 1 ) ≤ β(t, δ) h,s,a p π h (s, a) -p π h (s, a) 2 n t h (s, a) ≥ 1 -δ, with t 0 := inf{t : n t h (s, a) ≥ 1, ∀(h, s, a) s.t. sup π p π h (s) > 0}, and β(t, δ) := 4 log(1/δ)+12SH log(A(1+t)).
Imagine that a learner explores the MDP M using a fixed (stochastic) policy π exp , whose state-action distribution is ρ exp , and wants to figure out whether some policy π ε is ε-optimal or not. Then, after playing

π exp for K ≥ 1 episodes, E[n K h (s, a)] = Kρ exp h (s, a), so that the size of the confidence interval on V π ε 1 -V π 1 should roughly be β(K, δ) h,s,a p π h (s,a)-p π ε h (s,a) 2 Kρ exp h (s,a)
. Now, if the learner wishes to test whether π ε is ε-optimal it has to determine the sign of V π ε 1 -V π 1 + ε for all other policies π. To do that, it is sufficient to shrink the size of the confidence interval on

V π ε 1 -V π 1 below 1 2 |V π ε 1 -V π 1 + ε| = 1 2 |∆(π) -∆(π ε )
+ ε| for all policies π. Solving for the minimal K that satisfies this condition, we see that playing roughly

K(π exp , π ε ) ∝ log(1/δ) max π∈Π D s,a,h p π h (s, a) -p π ε h (s, a) 2 ρ exp h (s, a)(∆(π) -∆(π ε ) + ε) 2
episodes using the exploration policy π exp is enough to determine whether π ε is ε-optimal. Since the learner has the liberty to return any ε-optimal policy using any exploration policy, the lower bound corresponds to the minimum of K(π exp , π ε ) with respect to these two variables.

4 Towards a matching upper bound

Review of existing upper bounds

In this section, we review the main instance-dependent bounds within the PAC RL literature. We restrict our review to works on approximate identification (i.e., the general case with ε ≥ 0).

PAC RL with a generative model [START_REF] Zanette | Almost horizon-free structure-aware best policy identification with a generative model[END_REF] were the first to propose an instancedependent PAC RL algorithm, called BESPOKE. In infinite-horizon tabular MDPs with a discount factor γ ∈ [0, 1) and when the agent has access to a simulator that can query observations from any state-action pair, BESPOKE finds an ε-optimal policy with a sample complexity of at most

O s,a min 1 (1 -γ) 3 ε 2 , Var[R(s, a)] + γ 2 Var s ∼p(.|s,a) [V (s )] max(∆sa, (1 -γ)ε) 2 + 1 (1 -γ) max(∆sa, (1 -γ)ε) log 1 δ ,
where

∆ sa = V (s) -Q (s, a)
is the value gap of state-action pair (s, a) and Var denotes the variance operator. A notable feature of this result is that the sample complexity of BESPOKE (i) scales as O(SA log(1/δ)/(1 -γ) 3 ε 2 ) in the worst-case, which is the conjectured minimax lower bound for the infinite-horizon discounted setting [START_REF] Gheshlaghi Azar | Minimax pac bounds on the sample complexity of reinforcement learning with a generative model[END_REF]; (ii) it can be significantly smaller than minimax whenever the MDP is such that playing different actions yields very different total rewards, i.e., when the value gaps (∆ sa ) s,a are large compared to ε. For the setting of episodic linear MDPs [START_REF] Jin | Provably efficient reinforcement learning with linear function approximation[END_REF], the GSS-E algorithm by Taupin et al. ( 2022) solves a G-optimal design to determine the sampling frequencies of each state-action pair. The sample complexity of GSS-E is upper bounded by

O dH 4 (min h,s,a =π (s) ∆ h (s, a) + ε) 2 (log(1/δ) + d) ,
where d is the feature dimension. Up to H factors, this result improves upon the Ω(d 2 H 2 /ε 2 ) minimax bound for this setting (Wagenmaker et al., 2022b) whenever the minimum value gap in M is large.

PAC RL without a generative model On top of the sub-optimality gaps which characterize the bounds above, the instance-dependent complexities feature an additional component when a generative model is not available: visitation probabilities. These constitute the price that PAC RL algorithms have to pay in order to navigate the MDP and collect observations from distant states. Existing high-probability bounds on the sample complexity are of the form7

P τ = O C Alg (M, ε) log 1 δ ≥ 1 -δ,
where C Alg (M, ε) is a complexity measure corresponding to a given algorithm Alg. For example, for the MOCA algorithm Wagenmaker et al. (2022a) obtain

C MOCA (M, ε) = H 2 H h=1 min π exp ∈Π S max s,a 1 p π exp h (s, a) min 1 ∆ h (s, a) 2 , W h (s) 2 ε 2 + H 4 OPT(M, ε) ε 2 ,
where W h (s) = sup π p π h (s) is the maximum reachability of state s at step h ∈ [H] and OPT(M, ε) is a set of near-optimal triplets (h, s, a). In the above bound, the contribution of a triplet (h, s, a) to the total complexity will be small when either (i) its value gap ∆ h (s, a) is large or (ii) it is hard to reach by any policy, that is W h (s) ε. This "local complexity" of (h, s, a) is weighted by 1/p π exp h (s, a), which is the (expected) number of episodes that the agent needs to play in order to reach (h, s, a) when using π exp as an exploration policy. Subsequent works have proposed alternative local complexity measure featuring policy gaps instead of value gaps [START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF]Wagenmaker and Jamieson, 2022;[START_REF] Al-Marjani | Active coverage for pac reinforcement learning[END_REF]. Policy gaps can be larger than value gaps. Notably, they always are in deterministic MDPs [START_REF] Tirinzoni | Near instance-optimal PAC reinforcement learning for deterministic MDPs[END_REF]. For instance, for the PRINCIPLE algorithm, [START_REF] Al-Marjani | Active coverage for pac reinforcement learning[END_REF] obtain

C PRINCIPLE (M, ε) = H 3 min π exp ∈Π S max h,s,a sup π∈Π S p π h (s, a) p π exp h (s, a) max(ε, ∆(π)) 2 ,
where we recall the definition of the policy gap ∆(π

) := V 1 -V π 1 .
Compared to the bound of MOCA, here the contribution of (h, s, a) is small when all policies visiting it are largely sub-optimal. This can be the case even when a is an optimal action in state s, provided that no optimal policy reaches (h, s) with positive probability. We note that, while the lower bound of Theorem 1 only applies to algorithms that output a deterministic policy (see Definition 1), PRINCIPLE is allowed to return a stochastic policy.

PEDEL: A near-optimal algorithm

The PEDEL algorithm proposed by Wagenmaker and Jamieson (2022) has the sample complexity bound which resembles the most the complexity measure in our lower bound. To introduce it, we define the minimum policy gap ∆ min := min π∈Π D \{π } ∆(π), where π is an arbitrary optimal policy (i.e., V π 1 = V 1 ). Note that ∆ min = 0 whenever multiple optimal policies exist.

While PEDEL tackles the more general setting of identifying a near-optimal policy in linear MDPs, when instantiated for the special case of tabular MDPs, the leading term in its sample complexity bound is

C PEDEL (M, ε) = H 4 H h=1 min ρ∈Ω max π∈Π D s,a p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 ,
where we ignore some additive lower-order term that is polynomial in S, A, H, log(1/δ) and log(1/ε).

The next proposition, proved in Appendix C, compares this complexity measure to our lower bound.

Proposition 1. For any MDP M, it holds that

C PEDEL (M, ε) ≤ 8H 5 C LB (M, ε) + 4H 6 (ε ∨ ∆ min ) 2 .
This shows that in MDPs in which the minimum policy gap is a constant w.r.t. other problem parameters, i.e., ∆ min = Ω(1), the complexity C PEDEL (M, ε) is only a factor H 5 away from the instance-dependent lower bound. The same conclusion holds when we are interested in the regime ε = Ω(1).

More generally, the next proposition provides a sufficient condition on M for PEDEL to be instanceoptimal up to polynomial multiplicative factors of the horizon, regardless of the values of ε and ∆ min . Let us define the following divergence measure between any pair of policies π, π :

d(π, π ) := h∈[H] TV(p π h , p π h ) 2 ,
where TV(p π h , p π h ) := 1 2 s,a |p π h (s, a) -p π h (s, a)| denotes the total variation distance. Proposition 2. Let ε > 0 and M be an MDP such that, for some constant c > 0, min

π ε ∈Π ε max π∈Π D :∆(π)≤ε∨∆min d(π ε , π) ≥ c.
(1)

Then, C PEDEL (M, ε) ≤ 2H 5 4 + H c C LB (M, ε).
Proposition 2 essentially states that, for MDPs where near-optimal policies are sufficiently "diverse" (in the sense that for every ε-optimal policy there exists a sufficiently distant near-optimal policy), the complexity of PEDEL matches our lower bound up to only multiplicative factors of H. There are several classes of MDPs where the "diversity" condition (1) is satisfied. For instance, it is sufficient to find two near-optimal policies π 1 , π 2 (i.e., such that ∆(π 1 ) ∨ ∆(π 2 ) ≤ ε ∨ ∆ min ) with max h TV(p π 1 h , p π 2 h ) = 1 to guarantee that (1) holds with c = 1/48 . This happens in either of these cases:

• π 1 and π 2 deterministically visit some state s at some stage h (i.e., p π 1 h (s) = p π 2 h (s) = 1) in which they play different actions (i.e., π 1 h (s) = π 2 h (s)). • π 1 and π 2 visit two disjoint sets of states at some stage h, i.e., {s :

p π 1 h (s) > 0}∩{s : p π 2 h (s) > 0} = ∅.
• π 1 and π 2 visit the same states with equal probabilities at some stage h (i.e., p π 1 h (s) = p π 2 h (s) for any s) at which they play different actions (i.e., π 1 h (s) = π 2 h (s) for all s). For instance, it is enough to have a constant reward at the last stage (i.e., for some α, r H (s, a) = α for all s, a).

Remark 2. Upon close inspection of its pseudocode, it seems that PEDEL was designed with the implicit assumption that ε = O(H/d 3/2 ), where d is the dimension of the linear MDP9 . When this assumption is not satisfied (e.g., when ε = Ω(1/d)), the sample complexity of PEDEL can actually be d times larger than C PEDEL (M, ε). We elaborate on this in Appendix C.3.

Conclusion and perspective

We proposed the first general instance-dependent lower bound for online PAC RL and proved that it is nearly matched by PEDEL (Wagenmaker and Jamieson, 2022). Unfortunately, the algorithm is computationally intractable as it enumerates and stores the set of deterministic policies, which is of size A SH , in order to eliminate suboptimal policies and solve an experimental design of the form

min ρ∈Ω max π∈Π s,a p π, h (s, a) 2 ρ h (s, a) , (2)
where Π ⊂ Π D is the set of active policies at iteration (initialized as Π 0 = Π D ) and p π, h (s, a) refers to the visitation probabilities of π under the empirical MDP M . Therefore, we ask the following question Is there a PAC RL algorithm that can (nearly) match our lower bound while requiring a polynomial computational complexity in the size of the MDP?

We believe that answering this question would shed light on the (still elusive) problem of instanceoptimality in PAC RL. Indeed, if the answer is negative then this would indicate a clear separation between MDPs and bandits, where we know that computationally-efficient instance-optimality is possible [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF][START_REF] Jedra | Optimal best-arm identification in linear bandits[END_REF].

As a starting point to answer the above question, it is natural to wonder whether it is possible to use the same policy-elimination approach as PEDEL while making it computationally efficient. This is precisely the idea of PRINCIPLE [START_REF] Al-Marjani | Active coverage for pac reinforcement learning[END_REF], which performs implicit policy elimination by adding linear constraints to the set of valid state-action distributions. However, while doing so, it only solves an upper bound on the "optimal" design (2) used by PEDEL of the form

min ρ∈Ω max η∈Ω max s,a η h (s, a) ρ h (s, a) ,
where Ω is the set of valid state-action distributions in M that satisfy certain near-optimality constraints. This makes the sample complexity of the polynomial-time algorithm PRINCIPLE strictly worse than that of PEDEL, thus not matching the lower bound. We leave as an open question whether an implicit policy elimination scheme can be made compatible with the optimal design (2), in which computing the objective itself seems to require enumerating all policies.

A Proof of Theorem 1

As mentioned before, our proof is inspired by the one from [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF]. The key differences are in Lemma 6 which explicits the shape of the characteristic time for the PAC RL problem and Lemma 4 which relies on a slightly different martingale construction to concentrate the likelihood ratio. Indeed, our martingale involves the expected number of visits to state-action pairs instead of the actual number of visits as in [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF], which is crucial to obtain the navigation constraints ρ ∈ Ω in the optimization program of the lower bound.

Notation For any π ε ∈ Π ε , we define the set of alternative MDPs that have the same transitions as M but in which π ε is no longer ε-optimal:

Alt (π ε ) := M ∈ M 1 : ∀(h, s, a), p h (•|s, a; M) = p h (•|s, a; M) and ∃π ∈ Π D , V M,π ε 1 < V M,π 1 -ε .
Finally, we define the characteristic time to learn that π ε is ε-optimal as

T (M, π ε , ε) := sup ρ∈Ω inf M∈Alt(π ε ) h,s,a ρ h (s, a) r M h (s, a) -r M h (s, a) 2 2 -1
.

Further, for any set of MDPs E ⊂ M 1 , we let E denote the closure of E where the limit points are defined w.r.t. the distance d(M, M ) := max h,s,a |r M h (s, a) -r M h (s, a)|.

Proof. Let ξ ∈ (0, 1) and define

T := (1 -ξ) min π ε ∈Π ε T (M, π ε , ε) log(1/δ) 10
. Thanks to Markov's inequality we have that

E M [τ ] ≥ T (1 -P M (τ < T )). (3)
We will now upper bound the probability on the right-hand side above. Since the algorithm is (ε, δ)-PAC We have that

P M (τ < T ) = P M π / ∈ Π ε , τ < T + π ε ∈Π ε P M π = π ε , τ < T ≤ δ + π ε ∈Π ε P M π = π ε , τ < T . (4)
Now we fix π ε ∈ Π ε and apply Lemma 2 for the event C = π = π ε , τ < T ∈ F T , which yields that there exist M 1 , . . . , M SAH+1 ∈ Alt (π ε ) and (σ i ) 1≤i≤SAH+1 ∈ R SAH+1 + such that, for all y > 0,

P M π = π ε , τ < T ≤ exp y + T T (M, π ε , ε) max 1≤i≤SAH+1 P Mi ( π = π ε , τ < T + SAH+1 i=1 exp - y 2 2T σ 2 i = δ ξ-1 exp(y) max 1≤i≤SAH+1 P Mi ( π = π ε , τ < T + SAH+1 i=1 exp - y 2 2T σ 2 i .
(

) Now for any i ∈ [|1, SAH + 1|] since M i ∈ Alt (π ε ) there exists a sequence of MDPs (M n ) n≥1 with values in Alt (π ε ) such that lim n→∞ M n = M i 11 . 5
By definition of Alt (π ε ), we have that

P M n ( π = π ε , τ < T ≤ P M n ( π = π ε ) ≤ δ for all n ≥ 1. Therefore P Mi ( π = π ε , τ < T ≤ P Mi ( π = π ε ) (a) ≤ lim inf n→∞ P M n ( π = π ε ) ≤ δ, (6)
where (a) uses Fatou's lemma. Combining ( 5) with ( 6) for the value y = ξ log(1/δ)/2 yields

P M π = π ε , τ < T ≤ δ ξ exp(y) + SAH+1 i=1 exp - y 2 2T σ 2 i (a) = δ ξ/2 + SAH+1 i=1 exp - ξ 2 log(1/δ) 4(1 -ξ) min π ε ∈Π ε T (M, π ε , ε)σ 2 i , (7)
where (a) uses the definition of T . Therefore lim δ→0 P M π = π ε , τ < T = 0. This, combined with (4) gives that lim δ→0 P M (τ < T ) = 0. Plugging this back into (3) and using the definition of T yields

lim inf δ→0 E M [τ ] log(1/δ) ≥ (1 -ξ) min π ε ∈Π ε T (M, π ε , ε).
To finish the proof of Theorem 1, we take the limit when ξ goes to zero and use the simplified expression of the characteristic time given in Lemma 6.

A.1 The change-of-measure argument

Lemma 2. Consider ( M i ) 1≤i≤SAH+1 ∈ Alt (π ε ) SAH+1
given by Lemma 3 and let T ≥ 1. Then for any event C ∈ F T and any y > 0 we have

P M (C) ≤ exp y + T T (M, π ε , ε) max 1≤i≤SAH+1 P Mi (C) + SAH+1 i=1 exp - y 2 2T σ 2 i , where σ 2 i := H 2 4 d(M, M i ) 2 (1 + d(M, M i )) 2 .
Proof. Consider the simplex vector λ ∈ ∆ SAH+1 given by Lemma 3. We define the mixture distribution

Q = SAH+1 i=1
λ i P Mi and the corresponding log-likelihood ratio

L T (P M , Q) := log dP M dQ (H T ).
Using Lemma 3.1 from [START_REF] Garivier | Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models[END_REF] we have that for any event C ∈ F T and any x > 0,

P M (C) ≤ e x Q(C) + P M (L T (P M , Q) > x). ( 8
)
We bound each term in the right-hand side separately. Since λ ∈ ∆ SAH+1 , for any event C,

Q(C) = SAH+1 i=1 λ i P Mi (C) ≤ max 1≤i≤SAH+1 P Mi (C) (9)
On the other hand, we have that

L T (P M , Q) (a) ≤ SAH+1 i=1 λ i log dP M dP Mi (s t 1 , a t 1 , R t 1 , . . . , s t H , a t H , R t H ) 1≤t≤T = SAH+1 i=1 λ i L T (P M , P Mi ) (b) = SAH+1 i=1 λ i M T (P M , P Mi ) + SAH+1 i=1 λ i h,s,a E M [n T h (s, a)] r Mi h (s, a) -r M h (s, a) 2 2 = SAH+1 i=1 λ i M T (P M , P Mi ) + T SAH+1 i=1 λ i h,s,a E M [n T h (s, a)] T r Mi h (s, a) -r M h (s, a) 2 2 (c) ≤ SAH+1 i=1 λ i M T (P M , P Mi ) + T T (M, π ε , ε) ,
where (a) uses the convexity of x → log(1/x) and Jensen's inequality, (b) uses Lemma 4 and (c) uses the second statement of Lemma 3 and the fact that the vector

E M [n T h (s,a)] T
h,s,a belongs to Ω(M). Therefore for any y > 0, we have that

P M L T (P M , Q) > T T (M, π ε , ε) + y ≤ P M SAH+1 i=1 λ i M T (P M , P Mi ) > y ≤ SAH+1 i=1 P M M T (P M , P Mi ) > y ≤ SAH+1 i=1 exp - y 2 2T σ 2 i , ( 10
)
where in the last line we defined

σ 2 i := H 2 4 d(M, M i ) 2 (1 + d(M, M i ))
2 and used Azuma-Hoeffding inequality along with Lemma 4. Combining ( 9) and ( 10) with ( 8) for x = T T (M,π ε ,ε) + y gives the result.

A.2 A max-min game formulation

We define ∆ SAH+1 := {λ ∈ R SAH+1 + : SAH+1 i=1 λ i = 1} to be the simplex of dimension SAH. Further, for any set of MDPs E ⊂ M 1 , we let E denote the closure of E where the convergence is defined w

.r.t. the distance d(M, M ) := max h,s,a |r M h (s, a) -r M h (s, a)|.
Conv(E) refers to the convex hull of E. Finally, we define the set of KL-divergence vectors generated by alternative instances in Alt (π ε ),

D(π ε ) := r M h (s, a) -r M h (s, a) 2 2 h,s,a ∈ R SAH s.t. M ∈ Alt (π ε ) . Lemma 3. Fix π ε ∈ Π ε .
Then there exists ρ ∈ Ω, λ ∈ ∆ SAH+1 and M 1 , . . . , M SAH+1 ∈ Alt (π ε ) such that

T (M, π ε , ε) -1 = SAH+1 i=1 λ i h,s,a ρ h (s, a) r Mi h (s, a) -r M h (s, a) 2 2 .
Furthermore, for any ρ ∈ Ω we have that

SAH+1 i=1 λ i h,s,a ρ h (s, a) r Mi h (s, a) -r M h (s, a) 2 2 ≤ T (M, π ε , ε) -1 .
Proof. Observe that we can rewrite the expression of the characteristic time T (M, π ε , ε) as follows,

T (M, π ε , ε) -1 = sup ρ∈Ω inf M∈Alt(π ε ) h,s,a ρ h (s, a) r M h (s, a) -r M h (s, a) 2 2 = sup ρ∈Ω inf d∈D(π ε ) ρ d = sup ρ∈Ω inf d∈D(π ε ) ρ d = sup ρ∈Ω inf d∈Conv(D(π ε )) ρ d, (11)
where Conv(D(π ε )) denotes the convex hull of D(π ε ). Now let (ρ , d ) be an optimal solution to (11). Since D(π ε ) ⊂ R SAH , by Carathéodory's extension theorem we have that there exists λ ∈ ∆ SAH+1 and d

1 , . . . , d SAH+1 ∈ D(π ε ) such that d = SAH+1 i=1 λ i d i . This means that there exists ρ ∈ Ω and M 1 , . . . , M SAH+1 ∈ Alt (π ε ) such that T (M, π ε , ε) -1 = (ρ ) d = SAH+1 i=1 λ i (ρ ) d i = SAH+1 i=1 λ i h,s,a ρ h (s, a) r Mi h (s, a) -r M h (s, a) 2 2 .
This proves the first statement. Now for the second statement, using Sion's minimax theorem [START_REF] Sion | On general minimax theorems[END_REF], Theorem 3.4) we know that

(ρ ) d = sup ρ∈Ω inf d∈Conv(D(π ε )) ρ d = inf d∈Conv(D(π ε )) sup ρ∈Ω ρ d,
i.e (ρ , d ) is a saddle point of (11). This means that for all ρ ∈ Ω

ρ d ≤ (ρ ) d = T (M, π ε , ε) -1 .
Expanding the left-hand side proves the second statement.

A.3 Log-likelihood ratio for MDPs with the same transition kernel

In the following we fix an algorithm A. For T ≥ 1 we define the history up to the end of episode T as

H T := (s t 1 , a t 1 , R t 1 , . . . , s t H , a t H , R t H , 1 (t ≤ τ δ )) 1≤t≤T .
For any MDP M, we write P M to denote the probability distribution over possible histories when A interacts with M 12 . Further (F T ) T ≥1 will denote the sigma algebra generated by (H T ) T ≥1 . Finally, for a pair of MDPs M, M, we define the log-likelihood ratio of observations at the end of any episode T 13

L T (P M , P M ) := log dP M dP M (H T ) = log T t=1 H h=1 exp -[R t h -r M h (s t h , a t h )] 2 /2 p M h-1 (s t h |s t h-1 , a t h-1 ) exp -[R t h -r M h (s t h , a t h )] 2 /2 p M h-1 (s t h |s t h-1 , a t h-1 )
.

Lemma 4. For any pair of MDPs M, M ∈ M 1 , there exists a martingale (under E M ) M T (P M , P M ) T ≥1

whose increments are H 2 4 d(M, M) 2 (1 + d(M, M)) 2 -subgaussian and such that the likelihood ratio at the end of episode T satisfies

L T (P M , P M ) = M T (P M , P M ) + h,s,a E M [n T h (s, a)] r M h (s, a) -r M h (s, a) 2 2 .
Proof. Using that the MDPs M and M share the same transition kernels and have Gausssian reward distributions with unit variance, we can simplify their log-likelihood ratio as follows,

L T (P M , P M ) = - 1 2 T t=1 H h=1 R t h -r M h (s t h , a t h ) 2 -R t h -r M h (s t h , a t h ) 2 = 1 2 h,s,a T t=1 1(s t h = s, a t h = a) R t h -r M h (s, a) 2 -R t h -r M h (s, a) 2 . ( 12
)
Now for any fixed (h, s, a) we can define r T h (s, a)

:= T t=1 1(s t h =s,a t h =a)R t h n T h (s,a)
if n T h (s, a) > 0 and r T h (s, a) := 0 otherwise. Then we can write that

T t=1 1(s t h = s, a t h = a) R t h -r M h (s h , a h ) 2 = T t=1 1(s t h = s, a t h = a) R t h -r T h (s, a) + r T h (s, a) -r M h (s, a) 2 = T t=1 1(s t h = s, a t h = a) R t h -r T h (s, a) 2 + r T h (s, a) -r M h (s, a) 2 + 2 r T h (s, a) -r M h (s, a) T t=1 1(s t h = s, a t h = a) R t h -r T h (s, a) =0 = T t=1 1(s t h = s, a t h = a) R t h -r T h (s, a) 2 + r T h (s, a) -r M h (s, a) 2 . ( 13
)
Similarly, one can show that

h,s,a T t=1 1(s t h = s, a t h = a) R t h -r M h (s t h , a t h ) 2 = T t=1 1(s t h = s, a t h = a) R t h -r T h (s, a) 2 + r T h (s, a) -r M h (s, a) 2 . ( 14
)
13 With the convention that p 0 (•|s 0 , a 0 ) = 1(s 1 = •) for all (s 0 , a 0 ). Also note that we have simplified the probabilities of choosing actions π t (a t h |s t h , a t h-1 , . . . , s t 1 , H t-1) and of stopping π t (τ δ = t|Ht) as they only depend on the history, therefore having the same value for M and M.

Combining equations ( 12), ( 13) and ( 14) we get that

L T (P M , P M ) = 1 2 h,s,a T t=1 1(s t h = s, a t h = a) r T h (s, a) -r M h (s, a) 2 -r T h (s, a) -r M h (s, a) 2 = 1 2 h,s,a n T h (s, a) r M h (s, a) -r M h (s, a) 2 r T h (s, a) -r M h (s, a) -r M h (s, a) . ( 15
)
Next we define the sequences

M T (h, s, a) := 1 2 n T h (s, a) r M h (s, a) -r M h (s, a) 2 r T h (s, a) -r M h (s, a) -r M h (s, a) -E M [n T h (s, a)] r M h (s, a) -r M h (s, a) 2 . M T (P M , P M ) := h,s,a M T (h, s, a).
Using (15) one can check that

L T (P M , P M ) = M T (P M , P M ) + h,s,a E M [n T h (s, a)] r M h (s, a) -r M h (s, a) 2 2 .
This proves the second statement. Now for the first statement we note that for T ≥ 2,

M T (P M , P M ) -M T -1 (P M , P M ) = 1 2 h,s,a r M h (s, a) -r M h (s, a) 1(s T h = s, a T h = a) 2R T h -r M h (s, a) -r M h (s, a) -P M (s T h = s, a T h = a) r M h (s, a) -r M h (s, a) 2 = 1 2 h,s,a r M h (s, a) -r M h (s, a) 1 s T h = s, a T h = a R T h -r M h (s, a) :=X T + 1 2 h,s,a r M h (s, a) -r M h (s, a) 2 1 s T h = s, a T h = a -P M s t h = s, a t h = a . :=Y T X T satisfies E[X T |F T -1 ] = E    1 2 h,s,a r M h (s, a) -r M h (s, a) E R T h -r M h (s, a) |S T h , A T h =0 F T -1    = 0 and X T = H h=1 X T,h where X T,h = r M h (s T h , a T h ) -r M h (s T h , a T h ) 2 R T h -r M h (s T h , a T h ) is subgaussian with variance d(M, M) 2 conditionally to F T -1 (using that R T h -r M h (s T h , a T h ) is 1-subgaussian). Therefore, by Lemma 5 stated below, X T is subgaussian with σ 2 X = H 2 d(M, M) 2 Y T satisfies E[Y T |F T -1 ] = 1 2 h,s,a r M h (s, a) -r M h (s, a) 2 E 1(s T h = s, a T h = a) -P M (s T h = s, a T h = a)|F T -1 = 0 and |Y T | ≤ Hd(M, M) 2 2 . Therefore Y T is subgaussian with σ 2 Y = H 2 d(M, M) 4 4 .
By Lemma 5, M T (P M , P M ) -M T -1 (P M , P M ) is conditionally subgaussian with variance

H 2 d(M, M) 2 (1 + d(M, M)) 2 4 .
Lemma 5 (sum of subgaussian random variables, e.g. [START_REF] Buldygin | Subgaussian random variables[END_REF]). Let X an Y be two random variables that are σ 2 X and σ 2 Y subgaussian respectively. Then X +Y is (σ X +σ Y ) 2 -subgaussian.

Proof. Using Hölder inequality and the definition of subgaussian variables, we can write, for any p ≥ 1, q ≥ 1 such that

1 p + 1 q = 1 E[exp t(X + Y ) ] = E[exp(tX) exp(tY )] ≤ E[exp(ptX)] 1/p E[exp(qtY )] 1/q ≤ exp p 2 t 2 σ 2 X 2 1/p exp q 2 t 2 σ 2 Y 2 1/q = exp t 2 (pσ 2 X + qσ 2 Y ) 2 .
The conclusion follows by choosing

p = σ X +σ Y σ X and q = σ X +σ Y σ Y for which pσ 2 X + qσ 2 Y = (σ X + σ Y ) 2 .
A.4 Simplifying the expression of the characteristic time Lemma 6. For any M ∈ M 1 and π ε ∈ Π ε we have

T (M, π ε , ε) = 2 inf ρ∈Ω max π∈Π D s,a,h p π h (s, a) -p π ε h (s, a) 2 ρ h (s, a)(∆(π) -∆(π ε ) + ε) 2 .
Proof. Let us first solve the inner minimization program in the definition of T (M, π ε , ε) -1 . Using the definition of Alt (π ε ), we have that

inf M∈Alt(π ε ) h,s,a ρ h (s, a) r M h (s,a)-r M h (s,a) 2 2 = min π∈Π D inf M:V M,π ε 1 <V M,π 1 -ε h,s,a ρ h (s, a) r M h (s,a)-r M h (s,a) 2 2 . ( 16
)
Now observe that we can rewrite

V M,π ε 1 < V M,π 1 -ε as linear constraint in the rewards of M: h,s,a (p π h (s, a) -p π ε h (s, a))r M h (s, a) > ε, ⇐⇒ h,s,a (p π h (s, a) -p π ε h (s, a)) r M h (s, a) -r M h (s, a) > V π ε 1 -V π 1 + ε, ⇐⇒ h,s,a (p π h (s, a) -p π ε h (s, a)) r M h (s, a) -r M h (s, a) > ∆(π) -∆(π ε ) + ε Therefore, letting u h (s, a) = r M h (s, a) -r M h (s,
(p π h (s,a)-p π ε h (s,a))u h (s,a)>∆(π)-∆(π ε )+ε h,s,a ρ h (s, a) u h (s, a) 2 2 = h,s,a (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) -∆(π ε ) + ε) 2 -1 .
Summing up all the inequalities, we conclude that

T (M, π ε , ε) -1 = 1 2 sup ρ∈Ω min π∈Π D h,s,a (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) -∆(π ε ) + ε) 2 -1 .

B Concentration results

We report here useful concentration results from previous literature.

sup x∈R n : n i=1 bix 2 i ≤c n i=1 q i x i = c n i=1 q 2 i b i .

B.1 Proof of Lemma 1

Proof. Fix any pair of policies π, π . We write

( V π,t 1 -V π ,t 1 ) -(V π 1 -V π 1 ) = (p π -p π ) ( r t -r) = h,s,a (p π h (s, a) -p π h (s, a))( r t h (s, a) -r h (s, a)) = h,s,a 1 a ∈ {π h (s), π h (s)} (p π h (s, a) -p π h (s, a))( r t h (s, a) -r h (s, a)),
where we used vector notation p π = [p π h (s, a)] h,s,a . Now applying Proposition 3 with δ = δ/(A 2SH ) and the set Z

= (h, s, a) | (h, s) ∈ [H] × S, a ∈ {π h (s), π h (s)} s.t. sup π p π h (s) > 0 we get that with probability at least 1 -δ , ∀t ≥ t 0 , h,s,a 1 a ∈ {π h (s), π h (s)} n t h (s, a) r t h (s, a) -r h (s, a) 2 ≤ 4 log(1/δ ) + 4SH log(A(1 + t)) := β(t, δ ),
where we used that |Z| ≤ 2SH. Next, for each pair of policies (π, π ) we use Proposition 4 with q = p π -p π which yields that

( V π,t 1 -V π ,t 1 ) -(V π 1 -V π 1 ) ≤ β(t, δ ) h,s,a 1 a ∈ {π h (s), π h (s)} p π h (s, a) -p π h (s, a) 2 n t h (s, a) = β(t, δ ) h,s,a p π h (s, a) -p π h (s, a) 2 n t h (s, a)
, with probability at least 1 -δ/(A 2SH ). We conclude the proof with a union bound over pairs of policies (π, π ) ∈ Π D × Π D and remarking that

β(t, δ ) = 4 log(1/δ) + 12SH log(A) + 4SH log(1 + t) ≤ β(t, δ).

C PEDEL

C.1 Proof of Proposition 1

First, let us introduce the intermediate complexity measure

C(M, ε) := min ρ∈Ω max π∈Π D s,a,h p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 . We start by showing that H 3 C(M, ε) ≤ C PEDEL (M, ε) ≤ H 5 C(M, ε). For h ∈ [H] consider any ρ ,h ∈ arg min ρ∈Ω max π∈Π D s,a p π h (s,a) 2 ρ h (s,a)(∆(π)∨ε∨∆min) 2 . Now, letting ρ := 1 H H h=1 ρ ,h , we see that since Ω is a convex set, ρ ∈ Ω. Furthermore, C(M, ε) = min ρ∈Ω max π∈Π D s,a,h p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 ≤ max π∈Π D s,a,h p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 (a) ≤ H h=1 max π∈Π D s,a p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 (b) ≤ H H h=1 max π∈Π D s,a p π h (s, a) 2 ρ ,h h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 = H H h=1 min ρ∈Ω max π∈Π D s,a p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 = H -3 C PEDEL (M, ε),
where (a) uses the fact that max π h f (π, h) ≤ h max π f (π, h) and (b) uses the crude bound ρ h (s, a) ≥ ρ ,h h (s, a)/H. On the other hand we have

C PEDEL (M, ε) = H 4 H h=1 min ρ∈Ω max π∈Π D s,a p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 ≤ H 4 H =1 min ρ∈Ω max π∈Π D s,a,h p π h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 = H 5 C(M, ε).
Therefore, we just proved that (20) where in the second inequality we used that ∆(π) + ε -∆(π ε ) ≤ 2(∆(π) ∨ ε ∨ ∆ min ). Combining ( 18) and ( 20) proves the first inequality.

H 3 C(M, ε) ≤ C PEDEL (M, ε) ≤ H 5 C(M, ε). ( 18

C.2 Proof of Proposition 2

Combining the first inequality in the sequence (20) with ( 18), we have that Plugging this into (21) and using that ( ) ≤ 2C LB (M, ε) as in (20) concludes the proof.

C.3 On the complexity of PEDEL in the moderate ε regime PEDEL has a loop structure where at each iteration it seeks to halve the precision of its estimate of the value for all the policies that are still active. Taking a closer look into the design of PEDEL, we notice that it starts the first iteration with the parameter 0 = log 2 d 3/2 H and ends at log 4 ε . From Theorem 7 in Wagenmaker and Jamieson (2022), we get that the number of episodes played during the initial iteration is

Proposition 3 .

 3 ( Lemma 26, Al-Marjani et al. (2023) 14 ) Let the reward distribution ν h (s, a) be 1-subgaussian with mean r h (s, a) for all (h, s, a), and let r t h (s, a) be the MLE of r h (s, a) using samples gathered until episode t. Let Z ⊆ [H] × S × A and Z := |Z|. With probability at least 1 -δ, for any t ≥ t 0 := inf{t :n t h (s, a) ≥ 1, ∀(h, s, a) ∈ Z},(h,s,a)∈Z n t h (s, a) r t h (s, a) -r h (s, a) 2 ≤ 4 log(1/δ) + 2Z log(1 + t). Proposition 4. ( Lemma 30, Al-Marjani et al. (2023)) Let n ∈ N, q, b ∈ R n with b having strictly positive entries, and c ∈ R ≥0 . Then,

)

  Now we compare C(M, ε) and C LB (M, ε). Using that a 2 ≤ 2(a -b) 2 + 2b 2 , we note that for any ρ ∈ Ω and anyπ ε ∈ Π ε , π) ∨ ε ∨ ∆ min ) 2 ≤ max π∈Π D s,a,h 2(p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + s,a,h 2p π ε h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 ≤ max π∈Π D s,a,h 2(p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + max π∈Π D s,a,h 2p π ε h (s, a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + s,a,h 2p π ε h (s, a) 2 ρ h (s, a)(ε ∨ ∆ min ) 2 . (19)Now let us define ρ 0 := arg min ρ∈Ω max π∈Π D s,a,h(p π h (s,a)-p π ε h (s,a)) 2 ρ h (s,a)(∆(π)∨ε∨∆min) 2 and ρ 1 := ρ 0 +p π ε 2 a) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) π h (s, a) -p π ε h (s, a)) 2 ρ 1 h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + s,a,h 2p π ε h (s, a) 2 ρ 1 h (s, a)(ε ∨ ∆ min ) π h (s, a) -p π ε h (s, a)) 2 ρ 0 h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + s,a,h 4p π ε h (s, a) 2 p π ε h (s, a)(ε ∨ ∆ min ) 2 a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) 2 + 4H (ε ∨ ∆ min ) 2 ,where (a) uses (19) and (b) uses the fact that for all (h, s, a), ρ1 h (s, a) ≥ max(ρ 0 h (s, a), p π ε h (s, a))/2. Since this holds for any π ε , a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) + ε -∆(π ε )) 2 + 4H (ε ∨ ∆ min ) 2 = 8C LB (M, ε) + 4H (ε ∨ ∆ min ) 2 ,

C

  PEDEL (M, ε) ≤ 4H 5 min π∈Π ε min ρ∈Ω max π∈Π D s,a,h (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(∆(π) ∨ ε ∨ ∆ min ) bound ( ) as a function of 1/(ε ∨ ∆ min ) 2 . We have ( ) ≥ min π∈Π ε min ρ∈Ω max π∈Π D :∆(π)≤ε∨∆min s,a,h (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(ε ∨ ∆ min ) 2 ≥ min π∈Π ε max π∈Π D :∆(π)≤ε∨∆min h∈[H] min ρ∈Ω s,a (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(ε ∨ ∆ min ) 2 ≥ min π∈Π ε max π∈Π D :∆(π)≤ε∨∆min h∈[H] min ρ∈P(S×A) s,a (p π h (s, a) -p π ε h (s, a)) 2 ρ h (s, a)(ε ∨ ∆ min ) 2 ∆ min ) 2 min π∈Π ε max π∈Π D :∆(π)≤ε∨∆min d(π ε , π) ≥ 4c (ε ∨ ∆ min ) 2 ,where the first equality uses that min ρ∈P(X ) x∈X f (x) ρ(x) = ( x∈X f (x)) 2 for any non-negative function f . This implies that 4H 6 (ε ∨ ∆ min )

  , running just the initial iteration of PEDEL requires the number of episodes C 0 := O d 3 H 4 log(|Π|/δ) min ρ∈Ω max π∈Π D s,a,h p π h (s, a) 2 ρ h (s, a) .

  a), the program in (16) is equivalent to

	min π∈Π D	inf u s.t: h (s,a))u h (s,a)>∆(π)-∆(π ε )+ε h (s,a)-p π ε (p π	h,s,a	ρ h (s, a)	u h (s, a) 2 2	.	(17)
	h,s,a
	Solving the KKT conditions of the previous program, we get that
	inf u s.t:
	h,s,a

P(X ) denotes the set of probability measures over a set X .

This setting encompasses any initial state distribution by adding a transition from s 1 with the desired probabilities.

Since the initial state s 1 is fixed, we drop it from the notation of value functions.

We trivially get results for Gaussian rewards with arbitrary variance σ 2 by multiplying our lower bounds by σ 2 .

Without a unique optimal state-action distribution, exact identification may not be even possible, as no algorithm may be able to stop in finite time and return an optimal policy w.h.p. while being (0, δ)-PAC on the whole family M 1 .

A random variable X is σ 2 -subgaussian if E[e λ(X-E[X])] ≤ e σ 2 λ 2 /2 for any λ ∈ R.

While we focus on the main complexity terms which scale with sub-optimality gaps, visitation probabilities, and log(1/δ), it is worth noting that existing upper bounds all feature lower-order terms in either of these variables.

This is because, due to the triangle inequality, max TV(p π ε h , p π 1 h ), TV(p π ε h , p π 2 h ) ≥ 1/2 for any π ε ∈ Π ε .

d = SAH in our tabular setting.

For simplicity, we assume the latter is an integer.

Recall that the convergence was defined w.r.t. the distance d(M, M ) := max h,s,a |r M h (s, a) -r M h (s, a)|

Since we will be considering the same algorithm A interacting with different MDPs, we do not index the probability distributions by A.

Note that, while[START_REF] Al-Marjani | Active coverage for pac reinforcement learning[END_REF] state this lemma for rewards bounded in [0, 1], they actually prove it for any 1-subgaussian distribution. Indeed, their proof simply combines the concentration result of[START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], which holds for any subgaussian distribution, with a trick from[START_REF] Réda | Dealing with misspecification in fixed-confidence linear top-m identification[END_REF].

Appendix

Table of Contents

When ε = Ω(1/d), we have that d 2 = Ω( 1 (ε∨∆(π)∨∆min) 2 ) for all policies π so that

Therefore when ε = Ω(1/SAH), we get that the sample complexity of PEDEL for tabular MDPs satisfies τ = Ω (SAH × C PEDEL (M, ε) log (1/δ)) , almost surely.


Arthur Marzinkowski
email: marzinkowski@cril.fr

Salem Benferat
email: benferat@cril.fr

Anastasia Paparrizou
email: paparrizou@cril.fr

Cédric Piette
email: piette@cril.fr

On object detection based on similarity measures from digital maps

Keywords: object detection, maps, similarity measures, wastewater networks' data

This paper deals with the problem of object detection from digital maps. We are interested in detecting objects in a map which are defined in the legend. We will explore different similarity measures to compare the legend objects to those detected in different areas of the map. Our object detection method is evaluated on maps representing wastewater networks. In particular, we are interested in the detection of objects that represent lifting stations and manholes. The ultimate goal, after detecting correctly the target objects, is to repair misfunctions or inconsistencies in the water supply or evacuation network. The experimental results show that our similarity measures give good accuracy results on the detection of the objects of the legends.

Introduction

This paper focuses on map-like data that represents wastewater networks. Objects of interest are described in the map legend, with a focus on the detection of objects that represent lifting stations and manholes. The principle is therefore to take the sub-images associated with the objects in the legend as the reference image. The goal is then to detect all parts of the map that are sufficiently similar to the reference image. This problem is known as template matching (e.g. [START_REF] Brunelli | Template Matching Techniques in Computer Vision: Theory and Practice[END_REF]) and is used in many applications processing images (e.g., [START_REF] Hashemi | Template matching advances and applications in image analysis[END_REF]). Even if the images to be processed are of high quality, it is often difficult to detect all the legend objects present in the map. This is particularly true for images or maps that represent wastewater networks as the one given in Figure 1. Indeed, let us consider a legend object that represents a manhole. At the level of the legend (see Figure 2), a manhole is described by a complex geometric figure: a full blue circle inside another circle. At the map level, in some areas of the map (as the one illustated in Figure 4.(a), manholes appear isolated and independent (even if the background is rarely white as in the legends). However, in general the manholes do not appear exactly as they are as described by the legends. Namely, they do not appear independently and well separated on a white background (as in the legend). In reality, we find some objects that are superimposed on each other (as illustrated by Figure 4.(b)), others are on non-white backgrounds, which evidently makes the task of detection difficult. It is clear in this case that it will not be useful to search for geometric figures which have exactly the same shape as those given in the legend, but rather search for shapes which are (sufficiently) similar.

One of the objectives of this paper is to study different measures of similarities which are adapted to our framework of study, namely the maps of wastewater networks. The field of water sciences (including wastewater networks's data management) is rich in heterogeneous data. There have recently been many works that call for the use of machine learning techniques (e.g., [START_REF] Huu Du Nguyen | The use of machine learning algorithms for evaluating water quality index: A survey and perspective[END_REF], [START_REF] Mounce | A comparative study of artificial neural network architectures for time series prediction of water distribution system flow data[END_REF], [START_REF] Meyer | Machine learning-based global maps of ecological variables and the challenge of assessing them[END_REF]) and classifiers ( [START_REF] Zhu | Deep convolutional capsule network for hyperspectral image spectral and spectral-spatial classification[END_REF]). On the management of wastewater network data, there are already works to detect objects of interest, such as manholes, from images (e.g., [START_REF] Chahinian | Automatic mapping of urban wastewater networks based on manhole cover locations[END_REF], [START_REF] Yu | Road manhole cover delineation using mobile laser scanning point cloud data[END_REF]). Existing work mainly used machine learning techniques on images to detect an object of interest which is the manhole (the most visible of urban networks). The work considered in this paper does not deal with images but with maps, and therefore can detect different objects identified in the legend of the map. An extra difficulty we face when dealing with maps is the heterogeneity of the data, meaning that the maps in our database come from different sources and may have different formats.

The rest of the paper is organized as follows. The next section presents the problem considered in the paper. Section 3 describes the approach we propose and the similarity measures for comparing the legend objects to segments of the map and extract the most plausible objects of interest. Section 4 presents the experimental results of our paper. The last section concludes the paper.

Problem description

The problem tackled in this paper concerns the management of heterogeneous information. The approach that is followed consists in transforming data of a different nature into a format that is easily exploitable by the Artificial Intelligence mechanisms of query answering. This is especially true for image type data or Portable Document Format (PDF) files, where it is important to extract their content and represent it as a factual database (which may or may not be uncertain). Figure 1 shows an example of the maps we have to manage. In order to be able to query it and exploit its content, it is necessary to identify the relevant objects it contains. The legend (often present in maps) is a good starting point for identifying objects of interest associated with the map.

Figure 2 contains the legend of the map, given in Figure 1, from a small village of south France (written in French). It gives four elements (or objects) important for the description of wastewater networks.

The first object of interest represent manholes. A manhole is a structure allowing the cleaning and the inspection of a pipe of a network of waste water. Manholes play an important role because they are the access points to the networks. They are placed at regular intervals on the network and at each bend and intersection of the network. Figure 3 gives an example of an image that contains such manholes. In Figure 2, we can find the representation of manholes on the maps and on the legends. A manhole is represented by a geometric figure: a blue circle included in another circle of black color.

Another important object is the so-called lifting station, which is a pump system used to raise the level of water. In the legend and maps, the lifting station is also represented by a geometric figure, more complex than the one associated with manholes. A lifting station Fig. 1: Wastewater network map for Gigean village in France is represented by a black circle inside a pink circle, the whole is attached to a pink arrow (appears below the manhole symbol in Figure 2).

In this paper, we focus on these two objects of sewerage networks. Note that these two objects are not represented in the same way on all maps. There are very few lift stations (six in all) on the map. On the other hand, the manholes are numerous in the maps (e.g., more than 800 manholes for Gigean) and are distributed in a non-uniform way. In some areas (which represent the most populated places), manholes are shown in a superimposed manner; which makes the task of detecting them very difficult.

Elements of wastewater networks

In the following sections, several terms in the field of sanitation networks will be used. We will therefore define them in the preamble:

-Manhole

The manhole is an opening allowing the cleaning and the inspection of a pipe. They are placed at regular intervals on the network and at each bend and intersection of the network (see Figure Figure 3).

-Lifting station The lifting station is an automatic pump system that is used to raise the level of water Fig. 2: Legend associated with Gigean map given in Figure 1, where "regard" means manhole and "poste de relevage" means lifting station that accumulates below the so-called discharge level. The waters that flow below this level cannot flow via gravity.

-Gravity The gravity is a pipe allowing the flow of the water without the use of a pump, using just the force of gravity.

Data on wastewater networks

As mentioned earlier, Figure 1 represents an example of data that we will work on. This is a map of the Gigean wastewater network in image form. Several symbols are visible on the legend such as manholes, lifting stations, discharges and gravity. We will first focus on the manholes and lifting stations because they are specific elements on the map.

3 The proposed approach

Extraction methods

The method we use in this work is referred in the literature as template matching method [START_REF] Cox | Template matching and measure of match in image processing[END_REF]. This method is widely used in order to find one or more elements in an image that are similar to another one used as reference. Recall that, the reference elements are those appearing in the legend of the map. The element matching is done by calculating a matching score between the reference element and each sub-region of the image. A sub-region is defined by the dimensions of the reference image. This operation is a convolution over the image.

Figures 5a, 5b and 5c (figures which are inspired by the document given in https:// towardsdatascience.com/intuitively-understanding-convolutions-for-deep-learning-1f6f42faee1), illustrate the main steps of our method. These steps are clearly similar to convolution operations (e.g., [START_REF] Gu | Recent advances in convolutional neural networks[END_REF]); with one of the main difference is that in a convolution operation the output The blue part, in Figures 5a, 5b and5c, represents the base image (in our example, the map of Gigean given in Figure 1) where we seek to detect the elements of interest (e.g., manholes and lifting stations).

The red part is the reference image which represents the description of the object that we seek to detect. In our example, the reference image can be the sub-image associated with a manhole, which is given by the legend (e.g., Figure 2).

The idea is to apply template matching techniques in order to detect references images in the map. More precisely, we propose to use the reference image (the red image) as a sliding window in order to iterate through all the sub-images (with the same size as the red image) of the base image (blue part).

At each iteration, we calculate a degree of matching or similarity between the sub-image of the reference image (image given by the legend) with the base image (in our case the Gigean map). We will use different similarity measures that are appropriate for image comparison. The results of all these degrees of similarity will be stored in a third matrix. In our example (Figures 5a, 5b and5c), the similarity matrix is represented by the gray color. To be more precise, each of the comparisons of the reference image, with different parts of the base image, results in a degree of similarity, stored in a cell of the gray matrix. Algorithm 1 summarizes our matching method based on similarity measures. The inputs to our algorithm are the two images: the base image (or the source image), denoted I, and the reference image, denoted J. Let (w1, h1) be the matrix's dimensions of the source image (base) and (w2, h2) be the reference's dimensions. The output of our algorithm is a similarity matrix, denoted S. This matrix is of size (w1 -w2, h1 -h2).

Indeed, only the sub-images of the base image which have the same dimension as the reference image are taken into account in the detection of objects. For each x and y coordinates of the similarity matrix S, the degree of similarity S[x, y] is the result of the application of a similarity function between the reference matrix J and the base sub-image I composed of the rows that are between x and x + w2 and the columns that are between y and y + h2.

The simarity matrix calculated by the algorithm will then be used to detect the objects of interest. Assuming that we seek to detect a single object, in this case we take the sub-image of the base image whose degree of associated similarity is maximum. In the general case of multiple object detection, we need to define a threshold above or below which we consider the similarity degree is good enough to represent the reference image. Once the similarity matrix is calculated by the Algorithm 1, a decision step must be added to it to determine which sub-images (or regions) of the map represent the reference image. In this paper, we first used a threshold to determine the list of regions of the map that may correspond to the objects we seek to detect. Then, we defined an algorithm for grouping very close regions which all potentially represent the detected objects. The difficult question posed here is whether two regions which are very close (namely, which are only a few pixels apart) correspond to a single object or to two different objects.

Matching measures

In this subsection, we present some similarity measures. We first introduce some notations. Let f and g be two matrices (not necessarily of the same size). These two matrices will intuitively encode the two images that are inputs of our algorithm (the base image and the reference image). These matrices will contain positive numbers where in our example will encode the luminosity of a pixel (typically the gray level or gray intensity of a pixel).

We denote by h the height of the image or matrix g and by w its width. We will also use the value n as n = w × h (the number of elements in g).

The matching measures are split in two main categories: intensity measures and correlation measure.

Intensity measures consist in computing the difference pixel by pixel between the reference image and the source image. The sum of squared differences method belongs to this category.

Sum of squared differences-based methods

The sum of squared differences is a pixel by pixel intensity differences measure. The lower the matching score is, the more similar the compared images are. The measures we will compare are the Root Mean Square Distance (RMS) and the Sum of Squared Differences or squared error (SSD). Formally:

-Sum of squared differences or squared error (SSD)

M SSD (f, g) = w-1 i=0 h-1 j=0 (f (i, j) -g(i, j)) 2 (1)
-Root mean square distance (RMS)

M RM S (f, g) = 1 n w-1 i=0 h-1 j=0 (f (i, j) -g(i, j)) 2 (2)
The formulas 1 and 2 are equivalent in the sense that SSD and RMS produce the same relative order. In practice, only SSD is used due to its lower computing cost [START_REF] Cox | Template matching and measure of match in image processing[END_REF]. Other measures similar to (SSD) and (RMS) have been used in the context of image or signal processing (e.g., [START_REF] Sun | Root mean square minimum distance as a quality metric for stochastic optical localization nanoscopy images[END_REF]).

For the SSD measure, when M SSD (f, g) = 0, then we have a perfect matching. The maximum score depends on the type of image processed. SSD is symmetric since M SSD (f, g) = M SSD (g, f ) and satisfies the triangular inequality as a classic distance measure. The SSD measure is used, for instance, to track objects in videos [START_REF] Nickels | Estimating uncertainty in SSD-based feature tracking[END_REF]. The reference image is extracted from the video and used as template for the next frames.

We will illustrate with an example the sensitivity of SSD to luminosity/intensity variations, which is one of the main drawback of this measure. 7a and7b. The two images contain the same object, except that the image, given in Figure 7b is a strongly darkened version of the image given in 7a. In fact, the image, given in Figure 7a, is directly taken from the source image 6. Our aim is to find the exact locations of the reference object in the original image (Figure 6) from both reference images given Figures 7a and7b.

Our algorithm based on the SSD measure is able to find the exact location of the template image 7a. However, it fails finding the original position of the darkened template. This is one Correlation measure Correlation measures are known to be a robust similarity measure that has been used in different application contexts (e.g. [START_REF] Hashemi | Template matching advances and applications in image analysis[END_REF]). In this section, we are interested in the normalized version of cross-correlation measure (NCC), given by Equation 3(see for instance [START_REF] Scambos | Application of image cross-correlation to the measurement of glacier velocity using satellite image data[END_REF] for its use in image correlation).

-Normalised cross-correlation(NCC)

M N CC (f, g) = w-1 i=0 h-1 j=0 f (i, j).g(i, j) ( w-1 i=0 h-1 j=0 f (i, j) 2 ) . ( w-1 i=0 h-1 j=0 g(i, j) 2 ) (3)
When using a normalized cross-correlation (NCC) measure, the higher the obtained similarity value, the more similar are the images to be compared.

In particular, when M N CC (f, f ) = 1 then we have a perfect matching, which is the maximum score for NCC. Similarly, the degree 0 is the minimal score for NCC.

The main reason for NCC being more robust is that it is less sensitive to luminosity variations [START_REF] Mohamad | Template matching using sum of squared difference and normalized cross correlation[END_REF] comparing to SSD measures. Indeed, consider again our example with the figures 6, 7a and 7b. The use of the NCC similarity measure has made it possible to detect the object of interest from the two reference images (7a and 7b) which was not the case with SSD. This illustrates the robustness of NCC even with really high variations of luminosity.

We now illustrate different similarity measures on academic examples. Let us consider two grey scale source images represented by the matrices I 1 and I 2 respectively. These two matrices are of dimensions 3 x 3. These two images are such that ∀i ∈ {0, 1, 2}, ∀j ∈ {0, 1, 2}, I 2 (i, j) = I 1 (i, j)/2.

We also assume that we have a unique reference image T of dimensions 2x2: The four matrices (S 1 , ..., S 4 ) below give the similarity results, based on the two measures SSD and N, between the reference image T and each of the images sources I 1 and I 2 . Each matrix is of dimension 3x3. More precisely, the matrix S 1 (resp. S 3 ) is the result of applying the SSD similarity measure to the images I 1 and T (resp. I 3 and T ). Similary, the matrix S 2 (resp. S 4 ) is the result of applying the NCC similarity measure to the images I 1 and T (resp. I 3 and T ). We can observe that the matrices S 2 and S 4 , both obtained by using the NCC measure, are identical. This illustrates what was aforementioned, NCC is less sensitive to intensity variations on pixels. However, as indicated at the level of the array S 1 , the use of the SSD measure only allows to find (perfectly) the location of T in I 1 . However, when we apply SSD on the source image I 2 , we obtain a lower similarity score (a degree 0.5 in the matrix S 3 ,). This shows that SSD allows us to find reference images only if they are nearly identical to the original. Note that in our map example application, this should not be a problem. This is because there is not a large variation in pixel values between map items and the reference inside the legend.

I 1 =   10
The similarity measures seen so far have been defined on gray level images. These measurements can easily be extended to colored images. A natural solution is to simply apply the similarity measure on each channel (R, G, B) and thus sum up the result. This will give us a single similarity value on each pixel. To illustrate these similarity measures, we consider the following example with two colored images, simply denoted again as I 1 and I 2 . Again, I 2 is obtained by dividing each number in the I 1 matrix by 2:

I 1 =   (0, 0, 0)
(255, 0, 0) (0, 255, 0) (0, 0, 255) (255, 255, 0) (255, 0, 255) (0, 255, 255) (255, 255, 255) (127, 127, 127)

  I 2 =   (0, 0, 0)
(127, 0, 0) (0, 127, 0) (0, 0, 127) (127, 127, 0) (127, 0, 127) (0, 127, 127) (127, 127, 127) (63, 63, 63)   T = (0, 0, 0) (255, 0, 0) (0, 0, 255) (255, 255, 0)

As we did with grayscale images, we apply SSD and NCC to the two color source images I 1 and I 2 . We first add a matrix, S, which will be the result of non-normalized SSD on I 1 to illustrate the operation on different channels: S = 0. 520200. 260100. 374022. Let us consider for example the S[0, 1] = 520200. This example is simple to check, because we only have 255 and 0 as values. We so need to count the range of different channels (between 0 and 255 2 = 65025).

Below is the sub-matrix of I 1 in I[0, 1]:

S 1 = (255, 0, 0) (0, 255, 0) (255

Experimental Evaluation

This section presents the experimental results where the two main similarity measures, namely SDD and NCC, have been evaluated on the Gigean wastewater network map given in Figure 1. The Gigean map has been used as an PNG image with a resolution of (19850,14033) and using format RGB (3 bytes value per pixel) for representing the colored image. The experiments were conducted on a 12 core CPU 3.7GHz, 16Go RAM computer.

We used two reference images, extracted from the legend (given in Figure 2), associated with the objects of manholes and lifting stations. Table 1 gives the number of objects considered in our study.

Tables 2 and3 summarize the results obtained during our experiments.

Objects

Total number of objects Manholes 885 Lifting stations 5 The "Objects" column simply contains the two types of objects that our algorithm have to detect. The "Thresholds" column provides the different used thresholds. If the degree of similarity of a region, of the source image, is above (for NCC), or below (for normalized SSD) the threshold, then the region is considered to be sufficiently similar to the reference object. In this case, the region will therefore be considered as potentially containing the reference object.

The column "Candidate sub-images" indicates the number of elements of the similarity matrix which satisfy the threshold criteria. Specifically, this represents all sub-regions that have a sufficient similarity score to be considered as representing the reference image. However, multiple regions can represent a single object. The next column, "Detected Objects", specifies how many different detected objects exist on the map.

Therefore, the column "Detected objects" represents the number of detected objects once the sub-regions have been grouped. The algorithm that selects the set of detected objects from the candidate objects has a complexity of O(n 2 ). Consequently, when the number of candidate regions is too high (in our experiments above 200,000), it is not possible to accurately determine the number of detected objects (which explains the presence of the symbol "-" in the Table 2). Tables 4 and5 summarize running times for the computation of similarity scores (which is independent of the threshold) and for grouping algorithm.

Finally, the column "False positive" simply indicates the number of false positive. This represents the number of sub-regions that have a sufficient similarity score (therefore considered by our algorithm representing the reference objects) while the sub-region does not contain any reference object. Note that the detection of false positives is done manually.

In addition, the column "PCC" (Percent Correctly Classified) shows the ratio between the total number of elements to detect and the number of elements actually detected (after removing false positive). The column "False positive rate" provides the ratio between the number of false positive and the total number of object detected (false positive regions included). 8 is a black and white image representation of the similarity matrix (with a threshold equal to 0.9). Each white pixel in this image is a value of the similarity matrix whose value exceeds 0.9. Thus, each white pixel is the starting point of a valid candidate sub-image (of the source image). Future work is to develop efficient clustering algorithms for clustering areas that are sufficiently similar to be detected but they refer to the same object. Table 5: Running time when using normalized the normalized NCC on Gigean map Fig. 8: Image representation of similarity matrix with a threshold equal to 0.9

Figure 9 shows some rare cases of false positives recovered by NCC for lifting stations. Unlike using NCC for manhole detection, these false positives are more localized. Most of them are located in the pink region of the map like; in particular on certain texts written in pink color. False positives are almost non-existent (with a threshold of 0.9 for example) in the detection of manholes, this is due to the specific and proper manholes representation.

Conclusion and Further Work

In this paper, we studied the detection of multiple objects in the context of maps of wastewater networks. We particularly applied a template matching algorithms augmented with region grouping algorithm. We examined two similarity measures (i.e., the Sum of Squared Difference (SSD) and the Normalized Cross-Correlation (NCC)). We showed some advantages and drawbacks of those measures. The SSD measure is efficient at finding exact replicates of the Fig. 9: False positive example with NCC on lifting station reference image inside the source image, but intensity variation can deteriorate the results, even though they seem visually identical. The NCC measure on the other hand is more tolerant with those variations, though it can lead to more incorrect results. We tested both measures on the wastewater network map for Gigean with both manhole and lifting station. SSD brings more accurate results in object detection than NCC. We concluded that this was due to an overall high brightness across the whole image. Experimental results showed that it is the appropriate method for punctual object detection in this digital map.

Still some questions remain open; the first one is how to choose the right threshold automatically, namely, without any prior knowledge on the map (e.g., giving the number of elements inside it). The second is how to improve the region grouping algorithm. In this study we used a partitioning algorithm, but on high quality maps, the number of region matches can be quite high. Obviously, this limits the maximum number of objects we can detect and also the resolution of the images we operate on. One solution could be to assume that all matching regions that are adjacent in the similarity matrix represent a single object. Then, we can pick the location of the best score for the bounding box of the object. But, what if two different objects are so close that this assumption is wrong? This is still an open question.

Another direction is to study other types of elements in maps, like lines and areas of interest. Such types of elements cannot be grouped as easily as punctual ones, since defining a bounding box might not be a satisfying solution in such cases. Another problem to be solved is the automatic detection of those elements. Currently, the template images have been extracted manually in order to be able to have a general algorithm. A method of automatically detecting elements inside the legend, as well as labeling these elements, is under development.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Example of images representing a manhole Source: https://www.tubao.fr/tuyau-canalisation-pehd-reseaux-gravitaires

Fig. 5 :

 5 Fig. 5: Conceptual Illustrations of Convolution

Algorithm 1 :

 1 Similarity-based matching algorithm Input: Source image I Input: Reference image T Output: Similarity matrix S I ← Imgsrc; T ← Imgref ; foreach coordonates (x,y) in S do S[x, y] ← matching score(T, I[x, y : x + w2, y + h2]); end

Fig. 6 :

 6 Fig. 6: Fruit and vegetable image 1

Figure 6

 6 Figure 6 is an image of fruits and vegetables, considered as the source image. Let us now consider two examples of reference images, given by Figures7a and 7b. The two images contain the same object, except that the image, given in Figure7bis a strongly darkened version of the image given in 7a. In fact, the image, given in Figure7a, is directly taken from the source image 6. Our aim is to find the exact locations of the reference object in the original image (Figure6) from both reference images given Figures7a and 7b.Our algorithm based on the SSD measure is able to find the exact location of the template image 7a. However, it fails finding the original position of the darkened template. This is one

Fig. 7 :

 7 Fig. 7: Illustration of reference images

  , 255, 0) (255, 0, 255) This gives us S[0, 1] = 255 2 * 1 + 255 2 * 2 + 255 2 * 3 + 255 2 * 2 = 520200. NCC measures leads to identical results for I 1 and I 2 .

Table 1 :

 1 Number of manholes and lifting stations in the map

	Objects	Thresholds Candidate Detected False	PCC False positive
			sub-images objects positive		False rate
		0.10	30503	595	0	67.11%	0 %
	Manholes	0.148 0.15	79675 82215	726 730	1 1	81.80 % 82.25 %	0.13 % 0.13 %
		0.20	182934	942	157 88.58 %	16.66 %
		0.10	247	2	0	20 %	0 %
	Lifting stations	0.15 0.20	609 1375	3 5	0 0	40 % 80 %	0 % 0 %
		0.22	1932	6	0	100 %	0 %

Table 2 :

 2 Results of normalized SDD on Gigean map

	Objects	Thresholds Candidate Detected False	PCC False positive
			sub-images objects positive		False rate
		0.95	30984	598	0	67.45 %	0 %
	Manholes	0.935 0.9	31945 139101968	685 -	0 -	74.40 % -	0 % -
		0.85	242781641	-	-	-	-
		0.95	249	2	0	20 %	0 %
	Lifting stations	0.9	1613	5	0	80 %	0 %
		0.85	14890	8	2	100 %	25 %

Table 3 :

 3 Results of normalized NCC on Gigean map

Table 4 :

 4 Running time when using normalized the SDD measure on Gigean map Figure

https://monjardindidees.fr/optimisons-l-espace-au-potager

Acknowledgemnts This research has received support from the European Union's Horizon research and innovation programme under the MSCA (Marie Sk lodowska-Curie Actions)-SE (Staff Exchanges) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01, Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management). This research has also received support from the french national projet ANR CROQUIS (Collecte, représentation, complétion, fusion et interrogation de données de réseaux

d'eau urbains hétérogènes et incertaines) project, grant ANR-21-CE23-0004 of the French research funding agency (Agence Nationale de la Recherche ANR).