Alexander Afriat

Topology, holes and sources

come

The Aharonov-Bohm effect

A wavefunction is split into two, and these, having enclosed a (simply-connected) region ω containing a solenoid, are made to interfere on a screen. The enclosing wavefunction is sensitive to any enclosed electromagnetism inasmuch as the electromagnetic potential 1 A, a one-form, contributes a phase The electromagnetic field 2 F = dA produced by the solenoid is circumscribed to a middle region λ ⊂ ω surrounded by an isolating region 3 λ ′ = ω -λ where F vanishes but not A. The full Aharonov-Bohm effect 4 can be considered the 'differential' or 'incremental' sensitivity of the interference pattern to variations in the current through the solenoid. 5

1 By "potential" I just mean primitive: the potential of the electromagnetic two-form F = dA is its primitive A ↔ (A, ϕ), the potential of the magnetic two-form B = dA is its primitive A, the potential of the electric one-form * E = dϕ is its primitive ϕ (the Hodge dual * being taken in three dimensions), the potential of the three-form density ρ = dE is its primitive E.

2 It is perhaps easiest to think of F as a purely magnetic field B produced by the current density J = d * B in the solenoid.

3 It will be convenient to view λ and ω as concentric disks. 4 Ehrenberg & Siday (1949), [START_REF] Aharonov | Significance of electromagnetic potentials in the quantum theory[END_REF] 5 Cf. Batterman (2003, p. 555): "Similarly, in the AB effect, it appears that we will need to refer to different nonseparable holonomy properties for each case in which there is a different flux running through the solenoid." 1 2 The topological 1 interpretation I will distinguish between two (related but) different senses of "topological":

1. Topological 1 : related to the presence of a hole (containing a source, a solenoid or charge for instance).

2. Topological 2 : invariant under appropriate continuous deformations.

The topological 1 interpretation 6 of the Aharonov-Bohm effect can be formulated as follows: If A were closed throughout a simply-connected region ω it would also be 6 Aharonov & Bohm (1959, p. 490): "in a field-free multiply-connected region of space, the physical properties of the system still depend on the potentials." Wu & Yang (1975, p. 3845): "The famous Bohm-Aharonov experiment [ . . . ] showed that in a multiply connected region where fµν = 0 everywhere there are physical experiments for which the outcome depends on the loop integral [ . . . ] around an unshrinkable loop." And p. 3856: "fµν underdescribes electromagnetism because of the Bohm-Aharonov experiment which involves a doubly connected space region." Nash & Sen (1983, p. 301): "We [ . . . ] consider the consequence of assuming the field F to be identically zero in some region Ω. At first one may think that there will be no physically measurable electromagnetic effects in such a region Ω. This is not so, effects may arise if the topology of Ω is non-trivial, e.g. if Ω is not simply connected. [ . . . ] In terms of parallel transport one says that zero curvature does not imply trivial parallel transport if the region in which the curvature is zero is not simply connected. This underlies the fact that there is a sense in which the connection is a more fundamental object than the curvature, even though a connection is gauge dependent and not directly measurable." Ryder (1996, p. 101-4): "the Bohm-Aharonov effect owes its existence to the non-trivial topology of the vacuum [ . . . ]. The Bohm-Aharonov effect is the simplest illustration of the importance of topology in this branch of physics. [ . . . ] The relevant space in this problem is the space of the vacuum, i.e. the space outside the solenoid, and that space is not simply connected. [ . . . ] It is thus an essential condition for the Bohm-Aharonov effect to occur that the configuration space of the vacuum is not simply connected. [ . . . ] in other words, it is because the gauge group of electromagnetism, U 1 , is not simply connected that the Bohm-Aharonov effect is possible. [ . . . ] The configuration space of the Bohm-Aharonov experiment is the plane R 2 [ . . . ] with a hole in, and this is, topologically, the direct product of the line R 1 and the circle [ . . . ]. There is, nevertheless, a positive effect on the interference fringes. The mathematical reason for this is that the configuration space of the null field (vacuum) is the plane with a hole in [ . . . ]." Batterman (2003, p. 544): "We now have a U (1) bundle over a nonsimply connected base space: R 2 -{origin}. This fact is responsible for the AB effect." Ibid. pp. 552-3: "most discussions of the AB effect very quickly idealize the solenoid to an infinite line in space or spacetime. The flux, in this idealization, just is the abstract topological property of having space or spacetime be nonsimply connected. [ . . . ] The issue is whether the idealizations-[ . . . ] and nonsimply connected space in the AB effect-do better explanatory work than some less idealized description. I believe that the idealized descriptions do, in fact, do a better job." Ibid. p. 554: "It seems to me that for a full understanding of these anholonomies, one needs to appeal to the topology and geometry of the base space. [ . . . ] If we take seriously the idea that topological features of various spaces [ . . . ] can play an explanatory role [ . . . ]." Footnote 29, same page: "it is most fruitful to treat the AB solenoid as an idealization that results in the multiple connectedness of the base space of a fiber bundle." Ibid. p. 555: "The different cases are unified by the topological idealization of the solenoid as a string absent from spacetime which renders spacetime nonsimply connected. [ . . . ] This topological feature enables us to understand the common behaviour in different AB experiments [ . . . ]. [ . . . ] how can it possibly be the case that appeal to an idealization such as the AB solenoid as a line missing from spacetime, provides a better explanation of genuine physical phenomena than can a less idealized, more "realistic" account where one does not idealize so severely? [ . . . ] quite often [ . . . ] appeal to highly idealized models does, in fact, provide better explanations." Martin (2003, p. 48): "in the case of non-trivial spatial topologies, the gauge-invariant interpretation runs into potential complications. [ . . . ] So-called holonomies [ . . . ] encode physically significant information about the global features of the gauge field." See also Lyre (2001, pp. S377-80), [START_REF] Nounou | A fourth way to the Aharonov-Bohm effect[END_REF], Lyre (2004, p. 659), Agricola & Friedrich (2010, p. 275).

exact, and hence expressible as the gradient A = dµ of a zero-form µ; the flux

∂ω dµ = ω d 2 µ
through the boundary ∂ω would then vanish, as d 2 does. But here A is closed on λ ′ ; from dA = 0| λ ′ it does not follow that A is exact, nor that the flux through the enclosing loop vanishes: it may or may not.

The existence of the source responsible for the effect is therefore ruled out by one topology (A closed throughout a simply-connected region) but not another.

The same applies to a simply-connected three-dimensional region Ω enclosed by a two-dimensional boundary ∂Ω. If the two-form E were closed throughout Ω it would also be exact, and hence expressible as the curl E = dζ of a one-form ζ; the flux

∂Ω dζ = Ω d 2 ζ
through the boundary would then vanish. But if the region on which E is closed has a hole in it, the flux through the enclosing surface may or may not vanish.

This is precisely what we have in electrostatics, where the electric field E = * dϕ is (Hodge-dual to) the gradient dϕ of the scalar potential ϕ. The vanishing divergence dE expresses the conservation of electricity where none is created, away from the charges that produce E according to the Maxwell-Poisson equation dE = d * dϕ = ρ, ρ being the charge density. If the divergence dE vanished throughout the volume Ω, there would be no electricity produced and hence none radiated through the enclosing surface. 7 But a charge in Ω-say in a region 8 Λ ⊂ Ω isolated by Λ ′ = Ω -Λ-would prevent electricity from being conserved throughout Ω.

We have the same formalism in Newton-Poisson gravity, where ϕ is the gravitational potential, dϕ and E both represent gravitational force, and ρ is the mass density. Gravity 9 would therefore be another topological 1 effect.

Again, the topology of the region where the 'potential' (A or E or whatever) is closed tells us relatively little: if the region were simply-connected, conservation would be general within the enclosing surface since there could be no holes containing sources; and if nothing were created inside the enclosing surface, the total radiation through it would vanish. But if the topology does not allow the presence of holes to be ruled out, the presence of sources in them cannot either; and sources would produce a flux through the enclosing surface.

A non-trivial topology cannot, on its own at any rate, rule out the absence of a source either. Nor does it provide the 'amount' or 'intensity' of the possible source (which would tell us the intensity of the effect-the flux through the enclosing surface). So the full Aharonov-Bohm effect, which can be considered 'incremental,' is hardly topological 1 , or at any rate no more so than electrostatics or Newton-Poisson gravity.

The implications

([dA = 0| ω ] & [ω simply-connected]) ⇒ [A exact] ⇒ ∂ω A = 0
7 Over and above any divergence-free electrical background that may or may not be present. 8 It will be convenient to view Λ and Ω as concentric spheres. 9 Or rather the total gravitational attraction radiated by a mass.

are legitimate, unlike

([dA = 0| ω ] & ¬ [ω simply-connected]) ⇒ ¬ [A exact] ⇒ ¬ ∂ω A = 0 , or ([dA = 0| ω ] & [ω multiply-connected]) ⇒ [A not exact] ⇒ ∂ω A = 0 .
3 Topological 2 effects

Aharonov-Bohm

The Aharonov-Bohm effect is topological 2 in the sense that certain basic quantities (say the circulation C and resulting interference pattern) are invariant under appropriate continuous deformations; but it seems that (fundamental aspects of) electrostatics and Newton-Poisson gravity are just as topological 2 . Magnetostatics may be even more topological 2 . Since one measures the curvature F = dA = dA ′ rather than A itself, the freedom expressed by the substitution (2)

A → A ′ = A + dξ
(ξ being a zero-form) is invisible. Such transformations deform the level sets of A's local potential 10 γ. One can first imagine a purely 'radial' or 'angular' γ (with values running from zero to 2πk = C), 11 whose level lines are straight rays radiating through the annulus λ ′ from the inner disk λ to the edge ∂ω. A gauge transformation (2) would then deform the level rays, bending them without making them cross. The circle ∂ω can likewise be deformed into any loop going around the solenoid once. The Aharonov-Bohm effect is topological 2 in the sense that neither deformation affects the circulation C (or the resulting interference pattern).

It is perhaps easier to picture the denumerable set {γ 1 , . . . , γ N } of level curves at intervals of C/N than all of them; they will each be cut once 12 by any loop going around the solenoid once. 13 10 For wherever A is closed it can be written locally as the gradient A = dγ of a zero-form γ-just as E can be written locally, wherever it is closed, as the curl E = dζ of a one-form ζ.

11 Such a γ cannot be continuous everywhere; we can imagine a single discontinuity, say on the ray with values γ = 2πnk, where the integer n is zero then one, k = C/2π being a constant.

12 One should really say an odd number of times, as Jean-Philippe Nicolas has pointed out to me. Crossings in opposite directions cancel, and add nothing to the integral.

13 Batterman (2003, pp. 545-6): "The phase or anholonomy depends continuously on the flux in the solenoid, but [ . . . ] it depends discontinuously upon the shape of the circuit. For example, two loops around gives an anholonomy twice that of one loop around for constant magnetic flux." And p. 555: "The different cases are unified by the topological idealization of the solenoid as a string absent from spacetime which renders spacetime nonsimply connected. In this way we can understand why, for a given fixed magnetic flux, a loop that goes n times around the solenoid will have an anholonomy that is n times that of a loop that goes around once." A loop going around twice will cross each level curve twice. Alternatively, two different loops will also catch the same flux twice. Similar double-counting can be arranged in electrostatics too: a membrane enclosing the source twice, or two different membranes.

Whereas here the deformations are allowed by (and part of) theory, in the next cases they will be counterfactual.

Electrostatics

The basic law here, the Gauß-Maxwell equation ( 3)

∂Ω E = Ω dE = Ω ρ (or dE = ρ)
, is topological 2 inasmuch as the boundary ∂Ω and electric field lines can be continuously deformed without affecting the integral (3)-which corresponds to the (circulation giving rise to the) Aharonov-Bohm effect. We can imagine a spherically symmetric charge distribution ρ contained in Λ ⊂ Ω (everything concentric): the electrical field lines radiated by the charge in Λ correspond to the level rays radiating from the solenoid in λ. Nothing in electrostatics prevents the deformation of ∂Ω. Admittedly the electric rays cannot be bent without violating E = * dϕ; despite preserving the divergence dE = dE ′ , the transformation (4)

E → E ′ = E + dα (the three-dimensional version of (2), α being a one-form) is counterfactual-which does not prevent a conditional characterisation of the effect as topological 2 : "the integral would remain the same even if the field lines were bent."14 Most of this applies, mutatis mutandis, to Newton-Poisson gravity. Why bother with obvious facts about integration? Because much is made of the deformable loop ∂ω (which corresponds to the deformable surface ∂Ω) and gauge transformation (2) (which corresponds to the counterfactual transformation (4)).

Magnetostatics

The basic law here, Mawell's equation (or dB = 0), holds because a magnet has two poles, that act as source and sink of the same field lines, which form loops going from one pole to the other: all magnetism produced is eventually recovered. If a magnetic loop crosses the boundary ∂Ω it will cross it again15 on the way back to the magnet, thus erasing whatever it contributed to the integral on the way out. The law is topological 2 in that the boundary ∂Ω and field lines can be deformed16 continuously without affecting the integral. Nothing in magnetostatics prevents the deformation of ∂Ω; the deformation of the field lines by B → B ′ = B + dβ is again counterfactual, since the magnetic field is observable.

But if I dwell on these old three-dimensional theories I may give the impression I want to make a point about them, whereas my real point concerns the Aharonov-Bohm effect: it is hardly topological, or at any rate no more topological than electrostatics etc.

I thank Nazim Bouatta, Dennis Dieks, Éric Gourgoulhon, Marc Lachièze-Rey and Jean-Philippe Nicolas for valuable clarifications and corrections.

  wavefunction along) the boundary ∂ω and hence to the interference pattern on the screen. The electromagnetism on ω is related to the circulation around the boundary by

Here I am indebted to Dennis Dieks, Éric Gourgoulhon and Jean-Philippe Nicolas.

Here-returning to the point made by Jean-Philippe Nicolas-the number of perforations will be even: 0, 2, 4 etc.

Deformations of ∂Ω can of course lead to the exclusion or inclusion of certain loops.


Jérôme Renault
email: jerome.renault@tse-fr.eu.

General limit value in Dynamic Programming

Keywords: dynamic programming, average payoffs, discounted payoffs, general evaluations, limit value, vanishing impatience, uniform convergence of the values

come   L'archive ouverte pluridisciplinaire

Introduction

We consider a dynamic programming problem with arbitrary state space Z and bounded rewards. Is it possible to define in an unique way a possible limit value for the problem, where the "patience" of the decision-maker tends to infinity ?

For each evaluation (probability distribution over positive integers) θ = (θ t ) t≥1 , we consider the value function v θ of the problem where the initial state is arbitrary in Z and the weight of any stage t is given by θ t . The total variation of θ, that we also wall the impatience of θ, is defined by T V (θ) = ∞ t=1 |θ t+1 -θ t |. For instance, for each positive integer n the evaluation θ = (1/n, ..., 1/n, 0, ..., 0, ...) induces the value function vn corresponding to the maximization of the mean payoff for the first n stages; and for any λ in (0, 1] the evaluation θ = (λ(1 -λ) t-1 ) t induces the discounted value function v λ .

A well known theorem of Hardy and Littlewood (see e.g. [START_REF] Lippman | Criterion Equivalence in Discrete Dynamic Programming[END_REF] implies that for an uncontrolled problem, the pointwise convergence of (v n ) n , when n goes to infinity, and of (v λ ) λ , when λ goes to 0, are equivalent, and that in case of convergence both limits are the same. However, [START_REF] Lehrer | A uniform Tauberian Theorem in Dynamic Programming[END_REF] provided an example of a dynamic programming problem where (v n ) n and (v λ ) λ have different pointwise limits. But they also proved that the uniform convergence of (v n ) n and of (v λ ) λ are equivalent, with equality of the limit in case of convergence. And Sorin and [START_REF] Monderer | Asymptotic properties in Dynamic Programming[END_REF] extended this result to families of evaluations satisfying some conditions. Mertens and Neyman (1982) proved that when the family (v λ ) λ not only uniformly converges but has bounded variation, then the dynamic programming problem has a uniform value, in the sense that for all initial state z and ε > 0, there exists a play with mean payoffs from stage 1 to stage T at least v -ε provided T is large enough (see also [START_REF] Lehrer | Discounting versus Averaging in Dynamic Programming[END_REF]Sorin Moderer 1993 for proofs that the uniform convergence of (v λ ) λ or (v n ) n does not imply the existence of the uniform value of the problem). In this case of existence of a uniform value, one can show that all value functions v θ are close to v * , whenever θ is a non increasing evaluation with small θ 1 . The reason is that whenever θ is non increasing, the θ-payoff of a play can be expressed as a convex combination of the Cesàro values (v n ) n .

In the present paper, we investigate the uniform convergence of sequences (v θ k ) k when the "impatience" of the evaluations vanishes, in the sense that t |θ k t -θ k t+1 | → k→∞ 0. We will prove in theorem 2.5 that this uniform convergence happens if and only if the metric space {v θ k , k ≥ 1} (with the distance between functions given by the sup of their differences), is totally bounded. Moreover the uniform limit, whenever it exists, can only be the following function, which is independent of the particular chosen sequence (θ k ) k :

v * = inf θ∈Θ sup m≥0 v m,θ ,
where for each evaluation θ = (θ t ) t≥1 , the evaluation m, θ is defined as the evaluation with weight 0 for the first m stages and with weight θ t-m for stages t > m. Consequently, while speaking of uniform convergence of the value functions when the patience of the decision-maker tends to infinity, v * can be considered as the unique possible limit value. We also give simple conditions on the state space, the payoffs and the transitions (mainly compactness, continuity and non expansiveness) implying the uniform convergence of such value functions.

The paper is organized as follows: section 2 contains the model and the main results, which are shown to extend to the case of stochastic transitions. Section 3 contains a few examples and counterexamples and section 4 contains the proof of theorem 2.5. In the last section we formulate the following conjecture, which is shown to be true for uncontrolled problems: does the uniform convergence of (v n ) n , or equivalently of (v λ ) λ , implies the general convergence of the value functions, in the sense that:

∀ε > 0, ∃α > 0, ∀θ ∈ Θ s.t. T V (θ) ≤ α, v θ -v * ≤ ε ?
2 Model and results

General values in dynamic programming problems

We consider a dynamic programming problem given by a non empty set of states Z, a correspondence F with non empty values from Z to Z, and a mapping r from Z to [0, 1]. Z is called the set of states, F is the transition correspondence and r is the reward (or payoff) function. An initial state z 0 in Z defines the following dynamic programming problem: a decision maker, also called player, first has to select a new state z 1 in F (z 0 ), and is rewarded by r(z 1 ). Then he has to choose z 2 in F (z 1 ), has a payoff of r(z 2 ), etc... The decision maker is interested in maximizing his "long-term" payoffs, for whatever it means. From now on we fix Γ = (Z, F, r), and for every state z 0 we denote by Γ(z 0 ) = (Z, F, r, z 0 ) the corresponding problem with initial state z 0 . For z 0 in Z, a play at z 0 is a sequence s = (z 1 , ..., z t , ...) ∈ Z ∞ such that: ∀t ≥ 1, z t ∈ F (z t-1 ). We denote by S(z 0 ) the set of plays at z 0 , and by S = ∪ z 0 ∈Z S(z 0 ) the set of all plays. The set of bounded functions from Z to IR is denoted by V, and for v and v ′ in V we use the distance

d ∞ (v, v ′ ) = sup z∈Z |v(z) -v ′ (z)|.
Cesàro values. For n ≥ 1 and s = (z t ) t≥1 ∈ S, the average payoff of the play s up to stage n is defined by: γ n (s) = 1 n n t=1 r(z t ). And the n-stage average value of Γ(z 0 ) is: v n (z 0 ) = sup s∈S(z 0 ) γ n (s). By the Bellman-Shapley recursive formula, for all n and z we have:

n v n (z) = sup z ′ ∈F (z) (r(z ′ ) + (n -1) v n-1 (z ′ )) . We also have |v n (z) -sup z ′ ∈F (z) v n (z ′ )| ≤ 2 n , and a pointwise limit of (v n ) n should satisfy v(z) = sup z ′ ∈F (z) v(z ′ ) for all z. Discounted values. Given λ ∈ (0, 1], the λ-discounted payoff of a play s = (z t ) t≥1 is γ λ (s) = λ ∞ t=1 (1 -λ) t-1 r(z t )
, and the λ-discounted value at the initial state z 0 is v λ (z 0 ) = sup s∈S(z 0 ) γ λ (s). It is easily proved that v λ is the unique mapping in V satisyfing the fixed point equation :

∀z ∈ Z, v λ (z) = sup z ′ ∈F (z) (λ r(z ′ ) + (1 -λ) v λ (z ′ )) . It implies |v λ (z) -sup z ′ ∈F (z) v λ (z ′ )| ≤ λ, and a pointwise limit of (v λ ) λ should also satisfy v(z) = sup z ′ ∈F (z) v(z ′ ) for all z.
General values. We denote by Θ the set of probability distributions over positive integers. An element θ = (θ t ) t≥1 in Θ is called an evaluation.

Definition 2.1.

The θ-payoff of a play s = (z t ) t≥1 is γ θ (s) = ∞ t=1 θ t r(z t ), and the θ-value of Γ(z 0 ) is v θ (z 0 ) = sup s∈S(z 0 ) γ θ (s).
For each stage t we denote by δ t the Dirac mass on stage t and by n the Cesàro evaluation (1/n, ..., 1/n, 0, ..., 0, ...) = (1/n) n t=1 δ t , so that the notation v θ for θ = n coincide with the Cesàro-value v n , also written vn . It is easy to see that for each evaluation θ, the Bellman recursive formula can be written as follows:

v θ (z) = sup z ′ ∈F (z) (θ 1 r(z ′ ) + (1 -θ 1 ) v θ + (z ′ )) ,
where if θ 1 < 1, the "shifted" evaluation θ + is defined as ( θ t+1 1-θ 1 ) t≥1 .

Lemma 2.2. For all evaluation θ in Θ and state z in Z,

|v θ (z) -sup z ′ ∈F (z) v θ (z ′ )| ≤ θ 1 + t≥2 |θ t -θ t-1 |.
Proof: Consider any z 1 ∈ F (z), and for ε > 0 a play s = (z 2 , z 3 , ..., ) in S(z 1 ) such that γ θ (s) ≥ v θ (z 1 ) -ε. We have:

v θ (z) ≥ θ 1 r(z 1 ) + ∞ t=2 θ t r(z t ) ≥ θ 1 r(z 1 ) + ∞ t=2 θ t-1 r(z t ) + ∞ t=2 (θ t -θ t-1 )r(z t ) ≥ v θ (z 1 ) -ε - ∞ t=2 |θ t -θ t-1 |. Conversely, choose s = (z 1 , z 2 , ...) in S(z 0 ) such that γ θ (s) ≥ v θ (z) -ε. v θ (z) ≤ ε + θ 1 r(z 1 ) + ∞ t=2 θ t-1 r(z t ) + ∞ t=2 (θ t -θ t-1 )r(z t ) ≤ ε + θ 1 + v θ (z 1 ) + ∞ t=2 |θ t -θ t-1 |.
Definition 2.3. The total variation of an evaluation θ = (θ t ) t≥1 is

T V (θ) = ∞ t=1 |θ t+1 -θ t |.
We have sup t θ t ≤ T V (θ) ≤ 2. In the case of a Cesàro evaluation θ = (1/n, ..., 1/n, 0, 0, ...), we have T V (θ) = 1/n. For a discounted evaluation θ = (λ(1 -λ) t-1 ) t≥1 , we have T V (θ) = λ. A small T V (θ) corresponds to a patient evaluation, and sometimes we will refer to T V (θ) as the impatience of θ. We will consider here limits when T V (θ) goes to zero, generalizing the cases where n -→ ∞ or λ -→ 0.

Notice that if an evaluation θ is non increasing, i.e. satisfies θ t+1 ≤ θ t for all t, we have that T V (θ) = θ 1 . In the case of a sequence of non increasing evaluations

(θ k ) k , the condition T V (θ k ) ---→ k→∞ 0 is equivalent to the condition sup t≥1 θ k t ---→ k→∞ 0.
We always have:

(1 -θ 1 )

t≥1 |θ t -θ + t | ≤ θ 1 + T V (θ), so if T V (θ)
is small, the L 1 -distance between θ and the shifted evaluation θ + is also small. Notice also the following inequalities: for any given T , denote by θ(T ) the arithmetic mean of θ 1 ,..., θ T . We have for all t = 1, ..., T :

|θ t -θ(T )| ≤ T -1 t ′ =1 |θ t ′ -θ t ′ +1 | ≤ T V (θ).
So if T V (θ) is small, then for all T and t ≤ T , the weight θ t is close to the average θ(T ).

Given an evaluation θ and m ≥ 0, we write v m,θ for the value function associated to the evaluation θ ′ = ∞ t=1 θ t δ m+t . The following function will play a very important role in the sequel:

Definition 2.4. Define for all z in Z, v * (z) = inf θ∈Θ sup m≥0 v m,θ (z).

Main results

We now state the main result of this paper. Recall that a metric space is totally bounded, or precompact, if for all ε > 0 it can be covered by finitely many balls with radius ε.

Theorem 2.5. Let (θ k ) k≥1 be a sequence of evaluations such that T V (θ k ) ---→ k→∞ 0.
We have for all z in Z:

v * (z) = inf k≥1 sup m≥0 v m,θ k (z).
Moreover, the sequence (v θ k ) k uniformly converges if and only if the metric space ({v θ k , k ≥ 1}, d ∞ ) is totally bounded. And in case of convergence, the limit value is v * . This theorem generalizes theorem 3.10 in [START_REF] Renault | Uniform value in Dynamic Programming[END_REF], which was only dealing with Cesàro evaluations1 . In particular, there is a unique possible limit point for all sequences (v θ k ) k such that T V (θ k ) ---→ k→∞ 0, and consequently any (uniform) limit of such sequence is v * . Notice that this is not true if we replace uniform convergence by pointwise convergence: even for uncontrolled problems, it may happen that several limit points are possible. As an immediate corollary of theorem 2.5, when Z is finite the sequence (v θ k ) k is bounded and has a unique limit point, so converges to v * .

Corollary 2.6. Assume that Z is endowed with a distance d such that: a) (Z, d) is a precompact metric space, and b) the family (v θ ) θ∈Θ is uniformly equicontinuous. Then there is general uniform convergence of the value functions to v * , i.e.

∀ε > 0, ∃α > 0, ∀θ ∈ Θ s.t. T V (θ) ≤ α, v θ -v * ≤ ε.
The proof of corollary 2.6 from theorem 2.5 follows from 1) Ascoli's theorem, and 2) the fact that the convergence of (v θ k ) k to v * for each sequence of evaluations such that T V (θ k ) ---→ k→∞ 0 is enough to have the general uniform convergence of the value functions to v * .

Corollary 2.7. Assume that Z is endowed with a distance d such that: a) (Z, d) is a precompact metric space, b) r is uniformly continuous, and c)

F is non expansive, i.e. ∀z ∈ Z, ∀z ′ ∈ Z, ∀z 1 ∈ F (z), ∃z ′ 1 ∈ F (z ′ ) s.t. d(z 1 , z ′ 1 ) ≤ d(z, z ′
). Then we have the same conclusions as corollary 2.6, there is general uniform convergence of the value functions to v * , i.e.

∀ε > 0, ∃α > 0, ∀θ ∈ Θ s.t. T V (θ) ≤ α, v θ -v * ≤ ε.
Proof of corollary 2.7. One can proceed as in the proof of corollary 3.9 in [START_REF] Renault | Uniform value in Dynamic Programming[END_REF]. Given two states z and z ′ , one can construct inductively from each play s = (z t ) t≥1 at z a play s = (z ′ t ) t≥1 at z ′ such that d(z t , z ′ t ) ≤ d(z, z ′ ) for all t. Regarding payoffs, we introduce the modulus of continuity ε of r by: ε

(α) = sup z,z ′ s.t.d(z ,z ′ )≤α |r(z) -r(z ′ )| for each α ≥ 0. So |r(z) -r(z ′ )| ≤ ε(d(z, z ′ ))
for each pair of states z, z ′ , and ε is continuous at 0. Using the previous construction, we obtain that for z and z ′ in Z, for all k ≥ 1,

|v θ k (z) -v θ k (z ′ )| ≤ ε(d(z, z ′ )).
In particular, the family (v θ k ) k≥1 is uniformly continuous, and corollary 2.6 gives the result.

A completely different proof of corollary 2.7, with another expression for the limit value v * , can be found in theorem 3.9 of Renault Venel 2012.

Extension to stochastic transitions

We generalize here theorem 2.5 to the case of stochastic transitions. We will only consider transitions with finite support, and given a set X we denote by ∆ f (X) the set of probabilities with finite support over X. We consider now stochastic dynamic programming problems of the following form. There is an arbitrary non empty set of states X, a transition given by a multi-valued mapping F : X ⇉ ∆ f (X) with non empty values, and a payoff (or reward) function r : X → [0, 1]. The interpretation is that given an initial state x 0 in X, a decision-maker has to choose a probability with finite support u 1 in F (x 0 ), then x 1 is selected according to u 1 and there is a payoff r(x 1 ). Then the player has to select u 2 in F (x 1 ), x 2 is selected according to u 1 and the player receives the payoff r(x 2 ), etc... Following [START_REF] Maitra | Discrete gambling and stochastic games[END_REF], we say that Γ = (X, F, r) is a Gambling House. We assimilate an element x in X with its Dirac measure δ x in ∆(X), we write Z = ∆ f (X) and an element in Z is written u = x∈X u(x)δ x . In case the values of F only consist of Dirac measures on X, we are in the previous case of a dynamic programming problem.

We linearly extend r and F to ∆ f (X) by defining for each u in Z, the payoff r(u) = x∈X r(x)u(x) and the transition

F (u) = { x∈X u(x)f (x), s.t. f : X → Z and f (x) ∈ F (x) ∀x ∈ X}. A play at x 0 is a sequence σ = (u 1 , ..., u t , ...) ∈ Z ∞ such that u 1 ∈ F (x 0
) and u t+1 ∈ F (u t ) for each t ≥ 1, and we denote by Σ(x 0 ) the set of plays at x 0 . Given an evaluation θ, the θ-payoff of a play σ = (u 1 , ..., u t , ...) is defined as: γ θ (σ) = t≥1 θ t r(u t ), and the θ-value at x 0 is:

v θ (x 0 ) = sup σ∈Σ(x 0 ) γ θ (σ).
v θ is by definition a mapping from X to [0, 1], and we define as before, for all x in X:

v * (x) = inf θ∈Θ sup m≥0 v m,θ (x).
Theorem 1 easily extends to this context.

Theorem 2.8. Let (θ k ) k≥1 be a sequence of evaluations with vanishing total variation, i.e. such that T V (θ k ) ---→ k→∞ 0. We have:

∀x ∈ X, v * (x) = inf k≥1 sup m≥0 v m,θ k (x).
Moreover, the sequence (v θ k ) k uniformly converges if and only if the metric space

({v θ k , k ≥ 1}, d ∞
) is totally bounded. And in case of convergence, the limit value is v * .

Proof. Consider the deterministic dynamic programming problem Γ = (Z, F, r).

For any evaluation θ, the associated θ-value function ṽθ : Z -→ [0, 1] is the affine extension of v θ : X -→ [0, 1]. We put, as in definition 2.4, for all z in Z:

ṽ * (z) = inf θ∈Θ sup m≥0 ṽm,θ (z).
Notice that as an "infsup" of affine functions, there is no reason a priori for ṽ * to be affine. However, the restriction of ṽ * to X is v * . Consider now a sequence (θ k ) k≥1 of evaluations with vanishing total variation. Applying theorem 2.5 to Γ, we first obtain that for all x in X:

v * (x) = inf k≥1 sup m≥0 v m,θ k (x).
Moreover, given two evaluations θ and θ ′ , we have (using the same notation d ∞ for the distances on [0, 1] X and on [0, 1] Z ):

d ∞ (ṽ θ , ṽθ ′ ) = sup z∈Z |ṽ θ (z) -ṽθ ′ (z)|, = sup z∈Z | p∈X v θ (p) -v θ ′ (p)du(p)|, = d ∞ (v θ , v θ ′ ). Consequently, ({v θ k , k ≥ 1}, d ∞ ) is totally bounded if and only if ({v θ ′k , k ≥ 1}, d ∞
) is, and this completes the proof.

.

Examples

The first very simple example shows that, even when the set of states is finite, it is not possible to obtain the conclusions of theorem 2.5 or corollaries 2.6 and 2.7 with sequences of evaluations satisfying the weaker convergence condition: sup t≥1 θ k t -→ k→∞ 0.

Example 3.1. Consider the following dynamic programming problem with 2 states: Z = {z 0 , z 1 }, F (z 0 ) = {z 1 }, F (z 1 ) = {z 0 }, with payoffs r(z 0 ) = 0 and r(z 1 ) = 1. We have a deterministic Markov chain, so that any play alternates forever between z 0 and z 1 . Define for each k the evaluations

θ k = 1 k k t=1 δ 2t-1 and θ ′k = 1 k k t=1 δ 2t . We have v θ k (z 0 ) = v θ ′k (z 1 ) = 1,
and v θ k (z 1 ) = v θ ′k (z 0 ) = 0 for all k. Define now ν k as θ k when k is even, and θ ′k when k is odd. The evaluation ν k satisfies sup t ν k t = 1 k -→ k→∞ 0, however (v ν k (z 0 )) k and (v ν k (z 1 )) k do not converge. [START_REF] Lehrer | A uniform Tauberian Theorem in Dynamic Programming[END_REF] proved that the uniform convergence of the Cesàro values (v n ) n≥1 was equivalent to the uniform convergence of the discounted values (v λ ) λ∈(0,1] . The following example shows that this property does not extend to general evaluations: given 2 sequences of TV-vanishing evaluations (θ k ) k≥1 and (θ ′k ) k≥1 , the uniform convergence of (v θ k ) k and (v θ ′k ) k are not equivalent.

Example 3.2. In this example, (v n) n will pointwise converges to the constant 1/2 whereas for a particular sequence of evaluations (θ k ) k with total variation going to zero, we will have (v θ k ) k (z) = 1 for all k and z.

We construct a dynamic programming problem defined via a rooted tree T without terminal nodes (as in Sorin Monderer 1992 or [START_REF] Lehrer | Discounting versus Averaging in Dynamic Programming[END_REF]. T has countably many nodes, and the payoff attached to each node is either 0 or 1.

We first construct a tree T 1 , with countably many nodes and root z 0 . Each node has an outgoing degree one, except the root which has countably many potential successors z 1 , z 2 ,..., z n ... On the n th branch starting from z n , each node has a unique successor and the payoffs starting from z n are successively 0 for n stages, then 1 for n stages, then 0 until the end of the play. We now define T inductively from T 1 . T 2 is obtained from T 1 by attaching the tree T 1 to each node of T 1 \{z 0 }. This means that for each node z of T 1 \{z 0 } we add a copy of the tree T 1 where z plays the role of the root of T 1 . And for each l, the tree T l is obtained by attaching the tree T 1 to each node of T l-1 \T l-2 . Finally, T is defined as the union l≥1 T l .

T 1 z 0 £ £ £ £ £ £ £ £ ¢ ¢ ¢ ¢ ¢ ¢ ¡ ¡ ¡ ¡ d d e e e e f f f f f f £ £ £ £ £ £ £ £ n 0
Starting from z 0 , any sequence of n consecutive payoffs of 1 has to be preceeded by n consecutive payoffs of 0, so vn (z 0 ) ≤ 1/2 for each n ≥ 1, and for each node z and even integer n it is possible to get exactly n/2 payoffs of 0 followed by n/2 payoffs of 1. Consequently one can deduce that (v n (z)) n converges to 1/2 for each state z. But sup z∈Z v n (z) = 1 for each n, and the convergence is not uniform.

Consider now for any k, the evaluation

θ k = (0, ...0, 1 K , ..., 1 K , 0, ...) = 1 K K t=1 δ t+K . We have v θ k (z) = 1 for all k and z, so (v θ k ) k uniformly converges to v * = 1.
Example 3.3. The condition ({v θ , θ ∈ Θ}, d ∞ ) totally bounded is satisfied with the hypotheses of corollary 2.6 or corollary 2.7, and is sufficient to obtain the general uniform convergence of the value functions. This condition turns out to be stronger than having ({v θ k , k ≥ 1}, d ∞ ) totally bounded for every sequence of evaluations with vanishing TV.

In the following example, there is no control and the state space Z is the set of all integers, with transition given by the shift: F (z) = {z + 1}. The payoffs are given by r(0) = 1 and r(z) = 0 for all z = 0. For all evaluations θ = (θ t ) t≥1 , we have sup z∈Z v θ (z) = sup t θ t , so we have general uniform convergence of the value functions to v * = 0.

For all positive t, we can consider the evaluation given by the Dirac measure on t. We have v δt (-t) = 1, and v δt (z) = 0 if z = -t. The set {v δt , t ≥ 1} is not totally bounded.

4 Proof of theorem 2.5

We start with a few notations and definitions. We define inductively a sequence of correspondences (F n ) n from Z to Z, by F 0 (z) = {z} for every state z, and ∀n ≥ 0,

F n+1 = F n • F (the composition being defined by G • H(z) = {z" ∈ Z, ∃z ′ ∈ H(z), z" ∈ G(z ′ )}).
F n (z) represents the set of states that the decision maker can reach in n stages from the initial state z. We also define for every state

z, G m (z) = m n=0 F n (z) and G ∞ (z) = ∞ n=0 F n (z). The set G ∞ (z)
is the set of states that the decision maker, starting from z, can reach in a finite number of stages.

For all θ in Θ, m ≥ 0 and initial state z, we clearly have:

v m,θ (z) = sup z ′ ∈F m (z) v θ (z ′ ) = sup s∈S(z) ∞ t=1 θ t r(z m+t ).
In the sequel, we fix a sequence of evaluations (θ k ) k≥1 such that T V (θ k ) ---→ k→∞ 0.

Lemma 4.1. For all m 0 ≥ 0 and z in Z,

lim inf k sup m≤m 0 v m,θ k (z) = lim inf k v θ k (z).
Proof: For each k, we have

v θ k (z) ≥ v 1,θ k (z) -θ k 1 -T V (θ k ) by lemma 2.2, so v θ k (z) ≥ v 1,θ k (z) -2T V (θ k ). Iterating, we obtain that: v θ k (z) ≥ sup m≤m 0 v m,θ k (z) -2m 0 T V (θ k ).
A key result is the following proposition, which is true for all evaluations θ.

Proposition 4.2. For all evaluations θ in Θ and initial state z in Z,

sup z ′ ∈G ∞ (z) v θ (z ′ ) ≥ lim sup k v θ k (z).
Proof of proposition 4.2 z and θ being fixed, put β = sup z ′ ∈G ∞ (z) v θ (z ′ ). Fix ε ∈ (0, 1], there exists T 0 such that ∞ t=T 0 +1 θ t ≤ ε, and fix T 1 ≥ T 0 /ε. For any play s = (z 1 , ..., z t , ...) in S(z), we have by definition of β that for all T , ∞ t=T +1 θ t-T r(z t ) ≤ β. Let m be a non negative integer, we define:

A m = (m+1)T 1 -1 T =mT 1 ∞ t=T +1 θ t-T r(z t ) ≤ T 1 β. A m = ∞ t=mT 1 +1 r(z t ) min{(m+1)T 1 -1,t-1} T =mT 1 θ t-T , ≥ (m+1)T 1 t=mT 1 +1 r(z t )(θ 1 + ... + θ t-mT 1 ), ≥ (1 -ε) (m+1)T 1 t=T 0 +mT 1 r(z t ), ≥ (1 -ε)   (m+1)T 1 t=1+mT 1 r(z t ) -(T 0 -1)   .
We obtain:

T 1 β ≥ (1 -ε)T 1 γ mT 1 ,T 1 (s) -(1 -ε)(T 0 -1), and
γ mT 1 ,T 1 (s) ≤ β 1 -ε + ε. (1)
We now consider γ θ k (s) for k large. We compute ∞ t=1 θ k t r(z t ) by dividing the stages into blocks of length T 1 . For each m ≥ 0, let θ k (m) be the Cesàro-average of θ k t , where t ranges from mT 1 + 1 to (m + 1)T 1 . Notice that for all such t, we have

|θ k t -θ k (m)| ≤ (m+1)T 1 -1 t ′ =mT 1 +1 |θ t ′ -θ t ′ +1 |.
We have:

(m+1)T 1 t=mT 1 +1 θ k t r(z t ) ≤ (m+1)T 1 t=mT 1 +1 θ k (m)r(z t ) + (m+1)T 1 t=mT 1 +1 |θ k t -θ k (m)|r(z t ), ≤ θ k (m)γ mT 1 ,T 1 (s) + T 1 (m+1)T 1 -1 t=mT 1 +1 |θ k t -θ k t+1 |, ≤ θ k (m) β 1 -ε + ε + T 1 (m+1)T 1 -1 t=mT 1 +1 |θ k t -θ k t+1 |.
where the last inequality follows from equation (1). Summing up over m, we obtain: Proof: Consider an initial state z, and write α = inf k sup m v m,θ k (z). It is clear that α ≥ inf θ∈Θ sup m≥0 v m,θ (z). Now for each k ≥ 1 there exists m(k), such that v m(k),θ k (z) ≥ α -1/k, and we define the evaluation θ ′k = ∞ t=m(k)+1 θ k t-m(k) δ t . We have T V (θ ′k ) = T V (θ k ) ---→ k→∞ 0, so by proposition 4.2 we obtain that for all evaluations θ, sup z ′ ∈G ∞ (z) v θ (z ′ ) ≥ lim sup k v θ m(k),k (z) ≥ α.

γ θ k (s) ≤ β 1 -ε + ε + T 1 T V (θ k ). Consequently, lim sup k v θ k (z) ≤ β 1-ε + ε,
From lemma 4.1 and proposition 4.2, one can easily deduce the following corollary. And we can now conclude the proof the theorem 2.5, proceeding as in the proof of theorem 3.10 in [START_REF] Renault | Uniform value in Dynamic Programming[END_REF] End of the proof of theorem 2.5. Define d(z, z ′ ) = sup k≥1 |v θ k (z) -v θ k (z ′ )| for all states z and z ′ . The space (Z, d) is now a pseudometric space (may not be Hausdorff). By assumption, there exists a finite set of indices I such that for all k ≥ 1, there exists i in I satisfying d ∞ (v k θ , v i ) ≤ ε. Consider now the set {(v i (z)) i∈I , z ∈ Z}, it is a subset of the compact metric space [0, 1] I with the uniform distance, so it is itself precompact and we obtain the existence of a finite subset C of states in Z such that: ∀z ∈ Z, ∃c ∈ C, ∀i ∈ I, |v i (z) -v i (c)| ≤ ε.

We have obtained that for each ε > 0, there exists a finite subset C of Z such that for every z in Z, there is c ∈ C with d(z, c) ≤ ε. The pseudometric space (Z, d) is itself precompact. Equivalently, any sequence in Z admits a Cauchy subsequence for d. Notice that all value functions v θ k are clearly 1-Lipschitz for d.

Fix z in Z, and consider now the sequence of sets (G m (z)) m≥0 . For all m, G m (z) ⊂ G m+1 (z) so using the precompacity of (Z, d) it is not difficult to show (see, e.g. step 2 in the proof of theorem 3.7 in [START_REF] Renault | Uniform value in Dynamic Programming[END_REF]) that (G m (z)) m≥0 converges to G ∞ (z), in the sense that:

∀ε > 0, ∃m ≥ 0, ∀z ′ ∈ G ∞ (z), ∃z ′′ ∈ G m (z), d(z ′ , z ′′ ) ≤ ε.
(2)

We now use corollary 4.4 to conclude. We have for all m :

inf k≥1 sup z ′ ∈G m (z) v θ k (z ′ ) ≤ lim inf k v θ k (z) ≤ lim sup k v θ k (z) ≤ inf k≥1 sup z ′ ∈G ∞ (z) v θ k (z ′ ).
Fix finally ε > 0, and consider k ≥ 1 and m ≥ 0 given by equation (2). Let z ′ in G ∞ (z) be such that v θ k (z ′ ) ≥ sup z ′ ∈G ∞ (z) v θ k (z ′ ) -ε. Let z ′′ in G m (z) be such that d(z ′ , z ′′ ) ≤ ε. Since v θ k is 1-Lipschitz for d, we obtain v θ k (z ′′ ) ≥

  1 0........................................................ 0 0 1 1 0................................... 0........0 1........1 0........................... 0.............0 1.............1 0...........................

  and this is true for all ε.

Corollary 4. 4 .

 4 For all m 0 ≥ 0 and z in Z,inf k≥1 sup m≤m 0 v m,θ k (z) ≤ lim inf k v θ k (z) ≤ lim sup k v θ k (z) ≤ inf k≥1 sup m≥0 v m,θ k (z).

In this paper it is also proved that if the Cesàro values (v n) n uniformly converge then the limit can only be inf n≥1 sup m≥0 v m,n which in this case is also equal to sup m≥0 inf n≥1 v m,n .

The author gratefully acknowledges the support of the Agence Nationale de la Recherche, under grant ANR JEUDY, ANR-10-BLAN 0112.

We obtain lim inf k≥1 v θ k (z) ≥ lim sup k≥1 v θ k (z) -2ε, and so (v θ k (z)) k converges. Since (Z, d) is precompact and all v θ k are 1-Lipschitz, the convergence is uniform.

An open question

We know since [START_REF] Lehrer | A uniform Tauberian Theorem in Dynamic Programming[END_REF]

The above property is true in case of an uncontrolled problem (zero-player), i.e. when the transition F is single-valued.

Proposition 5.1. For an uncontrolled problem, the uniform convergence of the Cesàro values implies the general uniform convergence of the value functions:

Proof: Fix ε > 0. By assumption there exists N such that for all states z in Z, |v N (z) -v * (z)| ≤ ε. Consider an arbitrary evaluation θ and an initial state z 0 . For each positive t we denote by z t the state reached from z 0 in t stages, we have v θ (z 0 ) = ∞ t=1 θ t r(z t ) and v * (z 0 ) = v * (z t ) for all t. Divide the set of stages into consecutive blocks of length N: B 0 = {1, ..., N},..., B m = {mN + 1, ..., (m + 1)N},... Denote by θ(m) the mean of θ over B m , we have ∞ m=0 N θ(m) = 1. We also write r(m) for the mean 1 N t∈B m r(z t ). We have r(m) = vN (z mN ), so |r(m) -v * (z 0 )| ≤ ε for all m.

Computing payoffs by blocks, we have

So we obtain:

N θ(m)(r(m) -v * (z 0 )), and

If T V (θ) ≤ ε N , we get |v θ (z 0 ) -v * (z 0 )| ≤ 2ε, hence the result.