Nicolas Drougard

Didier Dubois

Jean-Loup Farges

Florent Teichteil-Königsbuch

Planning in Partially Observable Domains with Fuzzy Epistemic States and Probabilistic Dynamics

A new translation from Partially Observable MDP into Fully Observable MDP is described here. Unlike the classical translation, the resulting problem state space is finite, making MDP solvers able to solve this simplified version of the initial partially observable problem: this approach encodes agent beliefs with fuzzy measures over states, leading to an MDP whose state space is a finite set of epistemic states. After a short description of the POMDP framework as well as notions of Possibility Theory, the translation is described in a formal manner with semantic arguments. Then actual computations of this transformation are detailed, in order to highly benefit from the factored structure of the initial POMDP in the final MDP size reduction and structure. Finally size reduction and tractability of the resulting MDP is illustrated on a simple POMDP problem.

Introduction

It is claimed that Partially Observable Markov Decision Processes (POMDPs) [START_REF] Smallwood | The Optimal Control of Partially Observable Markov Processes Over a Finite Horizon[END_REF] finely models an agent acting under uncertainty in a partially hidden environment. However, solving a POMDP, i.e. the computation of an optimal strategy for the agent, is a really difficult task: the problem is PSPACE-complete [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF]. Classical approaches try to solve this problem using Dynamic Programming [START_REF] Cassandra | Incremental pruning: A simple, fast, exact method for partially observable markov decision processes[END_REF], or via approximate computation. These include for instance heuristic searches [START_REF] Smith | Heuristic search value iteration for POMDPs[END_REF] and Monte Carlo approaches [START_REF] Silver | Monte-carlo planning in large pomdps[END_REF].

The approach proposed here simplifies a POMDP problem before solving it. The transformation described leads to a fully observable MDP on a finite number of epistemic states, i.e. a problem modeling an agent acting under uncertainty in a fully observable environment [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. As such a finite state space MDP problem is P-complete [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF] this transformation qualifies as a simplification, and any MDP solver can return a policy for this translated POMDP.

Most of the POMDP algorithms draws upon the agent belief during the process, defined as the probability of the actual system state knowing all the system observations and agent actions from the beginning. This belief is updated at each time step using Bayes' rule and the new observation. The initial belief, or prior probability distribution over the system states, takes part in the definition of the POMDP. However in practice, the initial system state can be unknown: for instance, in a robotic exploration context, the initial location of the agent, or initial presence of an entity in the scene. Defining the process with a uniform probability distribution as initial belief (e.g. over all locations or over entity presence) is a subjectivist answer [START_REF] De Finetti | Wiley series in probability and mathematical statistics. Probability and mathematical statistics[END_REF], i.e. all probabilities are the same because no event is more plausible than another: it corresponds to equal betting rates. However the following belief updates will eventually mix up frequentist probability distributions defining the POMDP with the initial belief which is a subjective probability, and it does not always make sense.

More than only a simplification of the initial POMDP problem, the theoretical framework used here for the belief representation formally models an agent's knowledge about the system state: the proposed translation defines beliefs as possibility distributions over system states s ∈ S: these kinds of distributions are denoted by π (counterpart of probability notation p) and represent a fuzzy set of system states, as the indicator (chararacteristic) function of this set. Recall that the indicator function of a classical set A ⊆ S is 1 A (s) = 1 if s ∈ A and 0 otherwise. Values of a fuzzy set indicator function π are chosen in a finite and totally ordered scale L = { 1 = l 1 , l 2 , . . . , 0 } with l 1 > l 2 > . . . > 0 i.e. π : S → L. If s ∈ S is such that π(s) = l i , s is in the fuzzy set described by π, with degree l i . Possibilistic beliefs used in this work will represent fuzzy sets of possible states. If the current possibilistic belief coincide with the distribution π(s) = 1 ∀s ∈ S, all system states are totally possible, and it models therefore a total ignorance about the current system state: qualitative possibilistic beliefs can model agent initial ignorance. The perfect knowledge of the current state, say s ∈ S, is encoded by a possibility distribution equal to the classical indicator function of the singleton π(s) = 1 { s=s } (s). Between these two extrema, the current knowledge of the system is described by a set of entirely possible states, { s ∈ S s.t. π(s) = 1 }, and successive sets of less plausible ones { s ∈ S s.t. π(s) = l i } down to the set of impossible states { s ∈ S s.t. π(s) = 0 }.

The major originality of this work comes from the finiteness of the scale L: the number of possible beliefs about the system state is, as well, finite (smaller than #(L S ) = (#L) #S ), while the set of all probability distributions over S is infinite. The translation described here leads then to an MDP whose finite state space is the set of possible possibilistic beliefs, or epistemic states.

In addition to POMDP simplification and knowledge modelling, this qualitative possibilistic framework offers some interesting properties: the possibilistic counterpart of Bayes' rule leads to a special belief behaviour. Indeed the agent can possibly change their mind radically and rapidly, and under some conditions the increased specificity of the belief distribution is enforced, i.e. the knowledge about the current state is non decreasing with time steps [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF]. Finally, in order to fully define the resulting MDP, the translation has to attach a reward function to its states: as the new (epistemic) state of the problem is a possibility distribution, a dual measure, called necessity, can be computed from it. Defined as the Choquet integral using the necessity measure, the reward of an epistemic state is a pessimistic evalutation of the actual reward.

However the number of possibilistic belief distributions, or fuzzy epistemic states, grows exponentially with the number of initial POMDP system states. The so called simplification of the problem does not transform the PSPACE POMDP problem into a polynomial one: as the new state space size is exponential in the previous one, the resulting problem is EXPTIME. The proposed translation tries to generate as few epistemic states as possible taking carefully into account potential factorized structures of the initial POMDP.

The first section is devoted to the presentation of the Markov Decision Processes, the main concern of this paper. Tools from Possibility Theory are also defined to make this paper self-contained. Follows a section describing the first contribution of this work, which is the translation itself, presented in a formal way. As the resulting state space of the built MDP is too big to make this problem tractable without factorization tricks in practice, the next section details the proper way to preprocess its attributes. Finally, the last section illustrates the relevance of this approach with a simple robotic mission problem.

Background

The work developed in this paper remains in the classical MDP and POMDP frameworks, which are recalled in this section: possibilistic material necessary to build the promised translation are then presented.

Markov Decision Processes

A Markov Decision Process (MDP) [START_REF] Bellman | A Markovian Decision Process[END_REF] is a well suited framework for sequential decision making under uncertainty, when the agent involved has a full knowledge of the actual system state. Such a process is formally defined by a 4-tuple S, A, T, r where S is a finite set of system states s ∈ S. The finite set A consists of all actions a ∈ A available for the agent. The Markov dynamics of the system is described by the transition function T : S × A × S → [0, 1]. This function is defined as the transition probability distribution of the system states: if action a ∈ A is chosen by the agent, and the current system state is s ∈ S, the next state s ′ ∈ S is reached with probability T (s, a, s ′ ) = p ( s ′ | s, a ). Finally, a reward function r : S × A → R is defined to model the goal of the agent. Indeed, solving an infinite horizon MDP problem consists in computing a strategy, i.e. a function d defined on S and whose values are actions a ∈ A, maximizing the expected discounted total reward: E +∞ t=0 γ t • r ( s t , d t ) where d t = d(s t ) and 0 < γ < 1 is the discount factor.

A Partially Observable MDP (POMDP) [START_REF] Smallwood | The Optimal Control of Partially Observable Markov Processes Over a Finite Horizon[END_REF] makes a step further in the modeling flexibility, allowing the agent not to know which system state is the current one. The formal definition of a POMDP is the 7-tuple S, A, T, Ω, O, r, b 0 , where the system state S, the set of actions A, the transition function T and the reward function r remain the same as for the MDP definition. In this model, the current system state s ∈ S cannot be used as available information for the agent: the agent knowledge about the actual system state comes from observations o ∈ Ω, where Ω is a finite set. The observation function O : S × A × Ω → [0, 1] gives for each action a ∈ A and reached system state s ′ ∈ S, the probability over possible observations o ′ ∈ Ω: O(s ′ , a, o ′ ) = p ( o ′ | s ′ , a ). Finally, the initial belief b 0 : S → [0, 1] is the prior probability distribution over the state space S: b 0 (s) = p ( s 0 = s ), ∀s ∈ S.

At a given time step t > 0, the agent belief is defined as the probability of the t th system state s t conditionned on all the past actions and observations, and with the prior b 0 , i.e. b t (s) = p s0∼b0 ( s t = s | a 0 , o 1 , . . . , a t-1 , o t ). It can be easily recursively computed using Bayes' rule: at time step t, if the belief is b t , chosen action a ∈ A and new observation

o ′ ∈ Ω, next belief is b t+1 (s ′ ) ∝ O(s ′ , a, o ′ ) • s∈S T (s, a, s ′ ) • b t (s)
. Successive beliefs are computed with the observations perceived by the agent, and are then available during the process. Let us denote by P S the infinite set of probability distributions over S: seen as an MDP whose states are probabilistic beliefs, an optimal strategy for the infinite horizon POMDP is looked for among strategies d : P S → A such that successive d t = d(b t ) maximize the expected discounted total reward, which can be rewritten

E +∞ t=0 γ t • r ( s t , d t ) = E +∞ t=0 γ t • r ( b t , d t ) , (1)
defining r(b t , a) = s∈S r(s, a) • b t (s) as the reward of belief b t . As the focused problem (POMDP) has been formally defined, Possibilistic tools are now presented in the next section.

Possibility Theory

In our context, distributions defined in the Possibility Theory framework are valued in a totally ordered scale L = { 1 = l 1 , l 2 , . . . , 0 } with l 1 > l 2 > . . . > 0.

A possibility measure Π defined on S is a fuzzy measure valued in L, such that ∀A, B ⊂ S, Π(A ∪ B) = max { Π(A), Π(B) }, Π(∅) = 0 and Π(S) = 1. It follows that this measure is entirely defined by the associated possibility distribution, i.e. the measure of the singletons: ∀s ∈ S, π(s) = Π({ s }). Properties of this measure lead to the possibilistic normalization: max s∈S π(s) = Π(S) = 1. If s, s ∈ S are such that π(s) < π(s), it means that s is less plausible than s. States with possibility degree 0, i.e. states s ∈ S such that π(s) = 0, are impossible (same meaning as p(s) = 0), and those such that π(s) = 1 are entirely possible (but not necessary the most probable one).

After the introduction of a possibility measure over a set Ω, the joint possibility measure on S × Ω is defined in a qualitative way:

∀A ⊂ S, ∀B ⊂ Ω Π(A, B) = min { Π ( A | B ) , Π ( B ) } = min { Π ( B | A ) , Π ( A ) } . (2)
Note the similarities between Possibility and Probability Theory, replacing max by + and min by ×. Moreover, Possibility Theory has its own conditioning [START_REF] Dubois | The logical view of conditioning and its application to possibility and evidence theories[END_REF]:

Π ( A | B ) = 1 if Π(A, B) = Π(B) Π ( A, B ) otherwise (3)
which is nothing more than the least specific measure fulfilling the condition described by Equation 2. It can also be seen more easily as the joint measure normalized in a possibilistic manner. These tools from Qualitative Possibility Theory are enough to define the announced translation. Next section is then devoted to the building of an MDP with fuzzy epistemic states from a POMDP.

A Hybrid POMDP

As claimed by Zadeh, "most information/intelligent systems will be of hybrid type" [START_REF] Zadeh | Some reflections on soft computing, granular computing and their roles in the conception, design and utilization of information/intelligent systems[END_REF]: the idea developped here is to use a granulated representation of the agent knowledge using possibilistic beliefs instead of probabilistic beliefs in the POMDP framework. The first advantage of this granulation is that strategy computations are performed reasoning on a finite set of possibilistic beliefs (called then epistemic states): the set of all possibility distributions defined over S, denoted by Π S is the set L S without non-normalized functions, and then

#Π S = #L #S -(#L -1) #S , (4)
while the set of probability distributions over S is infinite. First, such beliefs are formally defined, as well as their own updates.

Possibilistic Belief

Consider that possibility distibutions similar to those used to define the initial POMDP are available: a transition distribution, giving the possibility degree of reaching s ′ ∈ S from s ∈ S using action a ∈ A, π ( s ′ | s, a ) ∈ L; as well as an observation one, giving the possibility degree of observing o ′ ∈ Ω, in a system state s ′ ∈ S after the use of a ∈ A, π ( o ′ | s ′ , a ) ∈ L. Indeed, this work is devoted to few kinds of practical problems: real problems modeled as POMDPs are often intractable. Our granulated approach is in this case a simplification of the initial POMDP, and possibility distributions are computed from the POMDP probability distributions, using a possibility-probability transformation [START_REF] Dubois | On possibility/probability transformations[END_REF]. On the other hand, some problems lead to POMDPs with partially defined probability distributions: some estimated probabilities have no strong guarantees. A more faithful representation is given with possibility distributions modeling the inherent imprecision, defining transition and observation possibility distributions. Let b π 0 : S → L be an initial possibilistic belief, normalized as any possibility distribution: max s∈S b π (s) = 1. As in the probabilistic case, possibilistic belief can be defined recursively using the possibilistic belief update [START_REF] Drougard | Qualitative Possibilistic Mixed-Observable MDPs[END_REF], derived from Bayes' rule based on the conditioning (3): at time step t, if the possibilistic belief is b π t , action a ∈ A and observation o ′ ∈ Ω specify the next belief

b π t+1 (s ′ ) = u(b π t , a, o ′ )(s ′ ) = 1 if π ( o ′ , s ′ | b π t , a ) = max s∈S π ( o ′ , s | b π t , a ) π ( o ′ , s ′ | b π t , a ) otherwise (5)
where the joint possibility distribution over

Ω × S π ( o ′ , s ′ | b π t , a ) is equal to max s∈S min { π ( o ′ | s ′ , a ) , π ( s ′ | s, a ) , b π t (s) }.
Note that keeping a qualitative view for the belief update, i.e. using the min operator to compute joint possibility distributions as defined in Equation 2, allows to reason on a finite set of beliefs, as no new values are created: the classical product is used in the quantitative part of the Possibility Theory, but is not considered in this work. Moreover, the use of the qualitative belief update has already been used in planning [START_REF] Drougard | Structured possibilistic planning using decision diagrams[END_REF].

Setting up Transition Functions

If the agent selects the action a ∈ A in the epistemic state b π ∈ Π S , the next epistemic state depends only on the next observation, as highlighted by possibilistic belief update [START_REF] De Finetti | Wiley series in probability and mathematical statistics. Probability and mathematical statistics[END_REF]. The probability distribution over observations conditionned on the reached state is part of the POMDP definition via the observation function O. The probability distribution over observations conditionned on the previous state is obtained using transition function

T : p ( o ′ | s, a ) = s ′ ∈S O(s ′ , a, o ′ ) • T (s, a, s ′
). This distribution and the possibilistic belief b π about the system state, can lead to an approximated probability distribution over the next observations. Indeed, a probability distribution over the system state, b π ∈ P S , can be derived from b π using extension of Laplace principle. Then approximate distribution over o ′ ∈ Ω is defined as

p ( o ′ | b π , a ) = s∈S p ( o ′ | s, a ) • b π (s). (6)
Finally, summing over concerned observations, the transition probability distribution over epistemic states is defined as

T (b π , a, (b π ) ′ ) = p ( (b π ) ′ | b π , a ) = o ′ |u(b π ,a,o ′ )=(b π ) ′ p ( o ′ | b π , a ) . (7)
A proper way to construct a probability distribution b π , from a possibility one b π , is the use of the pignistic transformation [START_REF] Dubois | Possibility theory and statistical reasoning[END_REF], minimizing the arbitrariness in the translation into probability distribution: numbering system states with the order induced by distribution b π , 1 = b π (s 1 ) b π (s 2 ) . . . b π (s #S+1 ) = 0, with s #S+1 an artificial state such that π(s #S+1 ) = 0 introduced to simplify the formula,

b π (s i ) = #S j=i b π (s j ) -b π (s j+1 ) j (8)
Note that this probability distribution corresponds to the center of gravity of the probability distributions family induced by the possibility measure defined by distribution b π [START_REF] Dubois | On possibility/probability transformations[END_REF], and respects the Laplace principle of Insufficient Reason (ignorance leads to uniform probability).

Reward Aggregation

After the transition function, it remains to assign a reward to each epistemic state: in the classical probabilistic translation, the reward assigned to a belief b is the reward expectation according to the probability distribution b: s∈S r(s, a)• b(s). Here, the agent knowledge is represented with a possibility distribution b π , which is less informative than a probability one: it accumulated uncertainty due to possibilistic discretization and due to possible agent ignorance. A way to define a reward being pessimistic about these uncertainties is to aggregate the reward using the dual measure of the possibility distribution, and the Choquet integral.

The dual measure of a possibility measure Π : 2 S → L is called necessity measure and is denoted by N . This measure is defined by ∀A ⊆ S, N (A) = 1-Π(A) where A is the complementary set of A : A = S \A. Recall notation L = { l 1 = 1, l 2 , l 3 , . . . , 0 }. For a given action a ∈ A, reward values, { r(s, a) | s ∈ S } are denoted by { r 1 , r 2 , . . . , r k } with r 1 > r 2 > . . . > r k , and k #S. An artificial value r k+1 = 0 is also introduced to simplify the formulae.

The discrete Choquet integral of the reward function with the necessity measure N is defined, and then simplified, as follows:

Ch(r, N ) = k i=1 (r i -r i+1 ) • N ( { r(s) r i } ) = #L-1 i=1 (l i -l i+1 ) • min s∈S s.t. π(s) li r(s). (9)
More on possibilistic Choquet integrals can be found in [START_REF] Cooman | Integration and conditioning in numerical possibility theory[END_REF]. This reward aggregation using the necessity measure leads to a pessimistic estimation of the reward: as an example, the reward min s∈S r(s, a) is assigned to the total ignorance. Note that, if the necessity measure N is replaced by a probability measure P, Choquet integral coincides with the expected reward based on P.

MDP with Epistemic States

This section summarizes the complete translation using the final equations of the previous sections. This translation takes for input a POMDP: S, A, T, Ω, O, r and returns an epistemic states based MDP: S, A, T , r . The state space is S = Π S . The (approximate) transition functions are T , such that ∀(b π , bπ ) ∈ Π 2 S , ∀a ∈ A, T (b π , a, bπ ) = p bπ b π , a defined with Equations 6 and 7. The reward of a belief b π is r(a, b π ) = Ch ( r(a, .), N b π ), defined with Equation 9and where N b π is the necessity measure computed from b π . Finally, as in the probabilistic framework (see Equation 1), the criterion of this MDP is the expected total reward:

E (b π t )∼ T +∞ t=0 γ t • r ( b π t , d t )
. While the resulting state space is finite, only really small POMDP problems can be solved with this translation without computation tricks. Indeed, Π S grows exponentially with the number of system states (see Equation 4), which makes the problem intractable even for state of the art MDP solvers.

Purely possibilistic counterparts of the (PO)MDPs, called Qualitative Possibilistic (PO)MDPs, have been already defined [START_REF] Sabbadin | A possibilistic model for qualitative sequential decision problems under uncertainty in partially observable environments[END_REF] and efficiently used for planning under uncertainty problems [START_REF] Drougard | Structured possibilistic planning using decision diagrams[END_REF]. These π-(PO)MDPs are quite different from the model exposed in this paper. For instance, they do not use quantitative data as probabilities or rewards. Dynamics is described in a purely qualitative possibilistic way. Frequentist information about the problem cannot be encoded: these frameworks are indeed dedicated to situations where the probabilistic dynamic of the studied system is lacking. Moreover, possible values of the reward function are chosen among the degrees of the qualitative possibilistic scale. A commensurability assumption between reward and possibility degrees, i.e. a meaning of why they share the same scale, is needed to use the criteria proposed in these frameworks. Our model bypass these demands: a real number is assigned to each possibilistic belief (epistemic state), using the Choquet integral, instead of a qualitative utility degree: it represents the reward got by the agent when reaching this belief (in an MDP fashion) as detailed in Section 3.3. Moreover, the dynamics of our process is described with probability distributions: approximate probabilistic transition functions between current and next beliefs, or epistemic states, are given in Section 3.2. Finally, our model can be solved by any MDP solver in practice: it becomes eventually a classical probabilistic fully observable MDP whose state space is the finite set Π S . Here, the term hybrid is used because the beliefs only are defined as possibility distributions, and all variables keep a probabilistic dynamic: the agent reasons based on a possibilistic analysis of the system state (the possibilistic belief, or epistemic state), and transition probability distributions are defined for its epistemic states.

Benefit from Factorization

This section carefully derive a tractable MDP problem from a factored POMDP [START_REF] Boutilier | Computing optimal policies for partially observable decision processes using compact representations[END_REF]: the resulting MDP is equivalent to the former translation, but some factorization and computational tricks are described here to reduce its size and to make it factorized First, the definition of a factored POMDP is quickly outlined, followed by some notations about variable dependences helpful for describing how distributions are dealt with. Next, a classification of the state variables is made to strongly adapt computations according to the nature of the system state. The way how possibility distributions are defined is presented, and the description of the use of the possibilistic Bayes' rule in practice ends this section.

Factored POMDPs

Partially Observable Markov Decision Processes can be defined in a factorized way. The state space is described with Boolean variables of the set S = { s 1 , . . . , s m }: S = s 1 × . . . × s m . The notation S ′ = { s ′ 1 , . . . , s ′ m } is also used. The set of Boolean observation variables O = { o 1 , . . . , o n } describes also the observation space Ω = o 1 × . . . × o n . For simplicity, and as state s ∈ S and observation o ∈ Ω notations are no longer reused in this paper, only variables are denoted with these letters from now: s j ∈ S and o i ∈ O.

The factorized description continues defining, ∀j ∈ { 1, . . . , m } and ∀a ∈ A, a transition function T a j (S, s ′ j ) = p s ′ j S, a , about the state variable s ′ j . One observation function is also given for each observation variable:

O a i (S ′ , o ′ i ) = p ( o ′ i | s ′ 1 , . . . , s ′ m , a ), ∀i = 1, . . . ,
′ j ), s ′ j ) = p s ′ j P(s ′ j ), a and O a i (P(o ′ j ), o ′ i ) = p o ′ i | P(o ′ j ), a .
Finally, the following subset of S is useful to specify observation dynamics:

Q(o ′ i ) = s k ∈ S s.t. ∃s ′ j ∈ P(o ′ i ) s.t. s k ∈ P(s ′ j ) = ∪ s ′ j ∈P(o ′ i ) P(s ′ j ) ⊆ S.
Probability distributions of variables P(o ′ i ) profit also from previous rewritings: thanks to state variables independences, ∀i = 1, . . . , n,

p ( P(o ′ i ) | S, a ) = s ′ j ∈P(o ′ i ) T a j (P(s ′ j ), s ′ j ) = p ( P(o ′ i ) | Q(o ′ i ), a ) (10)
The observation probability distributions knowing previous state variables are

∀i = 1, . . . , n, p ( o ′ i | Q(o ′ i ), a ) = v∈2 P(o ′ i ) p ( o ′ i | v, a ) • p ( v | Q(o ′ i ), a ) . (11)
Therefore a possibilistic belief defined on 2 Q(o ′ i ) is enough to get the approximate probability distribution of an observation variable: such an epistemic state, leads to a probability distribution b π over 2 Q(o ′ i ) via the pignistic transformation [START_REF] Dubois | Possibility theory and statistical reasoning[END_REF]. The approximate probability distribution of the i th observation variable, factorized counterpart of Equation 6, is: ∀i = 1, . . . , n,

p ( o ′ i | b π , a ) = v∈2 Q(o ′ i ) p ( o ′ i | v, a ) • b π (v). (12)

State Variable Classification

State variables s ∈ S do not play the same role in the process: as already studied in the literature [START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF], some variables can be visible for the agent, and this mixedobservability leads to important computational simplifications. Moreover, some variables do not affect observation variables, and this structure profits in the final MDP complexity.

-A state variable s j is said to be visible,

if ∃o i ∈ O, observation vari- able, such that P(o ′ i ) = s ′ j and ∀a ∈ A, p o ′ i | s ′ j , a = 1 { o ′ i =s ′ j } i.e. if o ′ i = s ′ j almost surely.
The set of visible state variables is denoted by S v = { s v,1 , s v,2 , . . . , s v,mv }. The observation variables corresponding to the visible state variables can be removed from the set of observation variables: the number of observation variables becomes ñ = nm v .

-Inferred hidden variables are simply ∪ ñ i=1 P(o ′ i ), i.e. all hidden variables influencing (remaining) observation variables. The set of inferred hidden variables is S h = { s h,1 , s h,2 , . . . , s h,m h } and contains possibly visible variables.

-Non-inferred hidden variables or fully hidden variables, denoted by S f , consists of hidden state variables which do not influence any observation, i.e. all remaining state variables. The fully hidden variables are denoted by s f,1 , s f,2 , . . . , s f,m f , and the corresponding set is S f .

The classification allows to avoid some computations for visible variables: if s v ∈ S v , and o v is the associated observation, computations of the distribution over P(o ′ v ), Equation 10, and of the distribution over o ′ v , Equation 11, are unnecessary: the distribution over

s ′ v (= o ′ v ) needed is simply given by T a ( P(s ′ v ), s ′ v ). The counterpart of Equation 12 is then simply p ( s ′ v | b π , a ) = 2 P(s ′ v ) T a ( P(s ′ v ), s ′ v ) • b π (P(s ′ v )) (13)
where b π is the probability distribution over 2 P(s ′ v ) extracted from the possibilistic belief over the same space, using pignistic transformation (8).

Beliefs Process Definition and Handling

This section is meant to define marginal beliefs instead of a global one, in order to profit of the structure of the initial POMDP. Possibilistic belief distributions have different definitions according to which class of state variables they concern.

As visible state variables are directly observed, there is no uncertainty over these variables. Two epistemic states (possibilistic belief distribution) are possible for visible state variable s

′ v,j : b ′ v,T (s ′ v,j ) = 1 { s ′ v,j =⊤ } and b ′ v,F (s ′ v,j ) = 1 { s ′ v,j =⊥ } .
As a consequence, one Boolean variable β ′ v,j ∈ { ⊤, ⊥ } per visible state variables is enough to represent this belief distribution in practice: if

s ′ v,j = ⊤, then next belief is b ′ = b ′ v,T represented by belief variable assignment β ′ v,j = ⊤, otherwise, next belief is b ′ = b ′ v,F
, and β ′ v,j = ⊥. For each i ∈ 1, . . . , ñ, each inferred hidden variable constituting P(o ′ i ) is an input of the same possibilistic belief distribution: non-normalized belief is

∀i = 1, . . . , ñ, b′ (P(o ′ i )) = max v∈2 Q(o ′ i ) min { π ( o ′ i , P(o ′ i ) | v, a ) , b(v) } , (14)
where the joint possibility distributions over

o ′ i ×P(o ′ i ) are π ( o ′ i , P(o ′ i ) | Q(o ′ i ), a ) = min π ( o ′ i | P(o ′ i ), a ) , min s ′ j ∈P(o ′ i ) π s ′ j P(s ′ j ), a . The possibilistic nor- malization, ∀w ∈ 2 P(o ′ i ) , b ′ (w) = 1 if w ∈ argmax v∈2 P(o ′ i ) b′ (v); b′ (w) otherwise.
finalizes this rewriting of the belief update [START_REF] De Finetti | Wiley series in probability and mathematical statistics. Probability and mathematical statistics[END_REF]. In practice, if l = #L, and p i = #P(o ′ i ), the number of belief states is l 2 p i -(l -1) 2 p i , and then the number of belief variables is n h,i = ⌈log 2 (l 2 p i -(l -1) 2 p i )⌉. A belief variable of an inferred hidden state variable is denoted by β h .

For each j ∈ 1, . . . , m f , non-normalized belief defined on fully hidden variable s f,j is b′ (s ′ f,j ) = max

v∈2 P(s ′ f,j ) min π s ′ f,j v, a , b(v) , (15)
which leads to the actual new belief b ′ after the possibilistic normalization. As each fully hidden variable is considered independently from the others, the number of belief variables is n f = ⌈log 2 (l 2 -(l-1) 2 )⌉ = ⌈log 2 (2l-1)⌉. A belief variable of a fully hidden state variable is denoted by β f . Finally, the global epistemic

state is b ′ (S ′ ) = min min mv j=1 b ′ (s ′ v,j ), min ñ i=1 b ′ (P(o ′ i )), min m f k=1 b ′ (s ′ f,k
) . Note that the belief over the inferred hidden variables ( 14) and the distribution over observation variables [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF], need a belief distribution over Q(o ′ i ) ⊆ S. As well, the belief over the fully hidden state variables (15) needs a belief distribution over variables P(s ′ f,j ) ⊆ S. Moreover, a belief distribution over P(s ′ v,i ) ⊆ S is needed to define an approximate probability distribution over visible state variables [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. These beliefs can be computed marginalizing the global belief using the max operator over unused state variables.

Solving a POMDP with a Discrete MDP Solver

A practical version of the factored MDP achieved in the previous section is described here. A concrete POMDP problem and the resulting MDP illustrate then the state space size reduction of our detailed possibilistic translation.

Resulting Factored MDP

A belief update depends only on the next observation (see Equation 5): the transition of a belief is then deterministic conditionned on the next observation. A simple trick is used to keep this determinism in the final MDP: a f lipf lop Boolean variable is introduced, changing its state at each step, denoted by f . It artificially divides a classical time step of the POMDP into two phases. During the first phase, called the observation generation phase, non-identity transition functions are the probability distributions over observation variables [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF] and visible state variables [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. During the second phase, called the belief update phase, non-identity transition functions are the deterministic transitions of the belief variables: variables β v are updated knowing value of corresponding visible variable s v ; variables β 1 h , . . . , β n h,i h are updated knowing value of observation variables o i , and using update [START_REF] Sabbadin | A possibilistic model for qualitative sequential decision problems under uncertainty in partially observable environments[END_REF]; finally, variables β 1 f , . . . , β n f f are updated using update [START_REF] Sanner | Probabilistic track of the 2011 international planning competition[END_REF]. The state space is then defined as:

S = f × s 1 v × . . . × s mv v × o 1 × . . . × o ñ × β 1 v × . . . × β mv v × β 1 h × . . . × β ñ h × β 1 f × . . . × β m f f , where ∀i = 1, . . . , ñ, β i h represents Boolean variables β 1,i h , . . . , β n h,i ,i h
, and ∀k = 1, . . . , m f , β j f represents Boolean variables β 1,j f , . . . , β n f ,j f

. Figure 1 (ID) of the resulting MDP where β t represents all belief variables, and v t the visible variables: the flipflop variable f , observations and visible state variables. The resulting MDP is a factored MDP thanks to the flipflop trick.

For a Concrete POMDP

A problem inspired by the RockSample problem [START_REF] Smith | Heuristic search value iteration for POMDPs[END_REF] is described in this section to illustrate the factorized possibilistic discretization of the agent belief, from a factored POMDP: a rover is navigating in a place described by a finite number of locations l 1 , . . . , l n , and where stand m rocks. Some of these m rocks have an interest in the scientific mission of the rover, and it has to sample them. However, sampling a rock is an expensive operation. The rover is thus fitted with a long range sensor making him able to estimate if the rock has to be sampled. Finally operating time of the rover is limited, but its battery level is available.

Variables of this problem can now be set, and classified as in Section 4.3: as the battery level is directly observable by the agent (the rover), the set of visible state variables consists of the Boolean variables encoding it: S v = { B 1 , B 2 , . . . , B k }. The agent knows the different locations of the rocks, however the nature of each rock is estimated. The set of inferred hidden state variables consists of m Boolean variables R i encoding the nature of the i th rock, ⊤ for "scientifically good" and ⊥ otherwise: S h = { R 1 , R 2 , . . . , R m }. When the i th rock is observed using the sensor, it returns a noisy observation of the rock in { ⊤, ⊥ }, modeled by the Boolean variable O i : the set of observation variables is then O = { O 1 , O 2 , . . . , O m }. Finally, no localization equipment is provided: the agent estimates its location from its initial information, and its actions. Each location of the rover is formally described by a variable L j , which equals ⊤ if the rover is at the j th location, and ⊥ otherwise. The set of fully hidden variables consists thus of these n variables: S f = { L 1 , L 2 , . . . , L n }. Initial location is known, leading to a deterministic initial belief: b π 0 (S h ) = 1 if L 1 = ⊤ and L j = ⊥ ∀j = 1, and 0 otherwise. However initial nature of each rock is not known. Instead of a uniform probability distribution, the Possibility Theory allows to represent the initial ignorance about rock natures with the belief b π 0 (S h ) = 1, for each variable assignment.

Classical POMDP solvers are based on probabilistic beliefs over the state space defined by S h , S f and even S v if Mixed-Observability [START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF] is not taken into account. The approach presented in this paper leads to an MDP with a finite space of epistemic states. Finally, the factorization tricks lead to a reduction of the state space size: with a flat translation of this POMDP, ⌈log 2 (#L 2 n+m+k -(#L -1) 2 n+m+k )⌉ Boolean variables are necessary. Taking advantage of the POMDP structure, the resulting state space is encoded with 1 + 2k + m + (m + n)⌈log 2 (2#L -1)⌉ Boolean variables: the flipflop variable, the visible variables and associated beliefs variables, the observation variables, and the belief variables associated to the fully hidden and inferred hidden variables. Moreover, the dynamic of the resulting MDP is factored, and lot of transitions are deterministic, thanks to the flipflop variable trick. These simplifying structures are beneficial to the MDP solvers, leading to faster computations.

Conclusion

This paper describes a hydrid translation of a POMDP into a finite state space MDP one. The Qualitative Possibility Theory is used to maintain an epistemic state during the process: the belief space has a granulated representation, instead of a continuous one as in the classical translation. The resulting MDP is entirely defined computing transition and reward functions over these epistemic states. Definitions of these functions use respectively the pignistic transformation, used to recover a probability distribution from an epistemic state, and the Choquet integral with respect to the necessity, making the agent pessimistic about its ignorance. A practical way to implement this translation is then described: with these computation tricks, a factored POMDP leads to a factored and tractable MDP. This promising approach will be tested on the POMDPs of the IPPC competition [START_REF] Sanner | Probabilistic track of the 2011 international planning competition[END_REF] in a future work: provided problem descriptions are indeed in the form of the factored POMDPs introduced in Section 4.

Fig. 1 .

 1 Fig. 1. ID of the resulting MDP: thickest arrows are non-identity transitions.

  n and ∀a ∈ A. It is here understood that S ′ are independent conditionned on S and the action a, and that { o ′ i } Notations and Observation Functions Transitions of the final MDP make it more handy if each variable depends on only few previous variables: the procedure to avoid blocking such simplifications brought by the structure of the initial POMDP during the translation, needs the following notations. In practice, for each i ∈ { 1, . . . , n } not all state variables influence observation variable o ′ i ; similarly, for each j ∈ { 1, . . . , m }, not all current state variables influence next state variable s ′ j : observation variable o ′ i depends on some state variables which are called parents of o ′ i as they appears as "parents nodes" in a Bayesian network illustrating dependencies of the process, and denoted by P(o ′ i ) = s ′ j ∈ S ′ s.t. o ′ i depends on s ′ j . As well, probability distributions of next state variable s ′ j depend on some current state variables, denoted by P(s ′ j ) = s k ∈ S s.t. s ′ j depends on s k . It leads to the following rewriting of probability distributions: T a

	independent conditionned on S ′ and a.	n i=1 are
	4.2

j (P(s


Claude M Dion
email: claude.dion@umu.se

Svante Jonsell

Anders Kastberg
email: anders.kastberg@unice.fr

Peder Sjölund

Bimodal momentum distribution of laser-cooled atoms in optical lattices

We study, numerically and experimentally, the momentum distribution of atoms cooled in optical lattices. Using semi-classical simulations, we show that this distribution is bimodal, made up of a central feature corresponding to "cold", trapped atoms, with tails of "hot", untrapped atoms, and that this holds true also for very shallow potentials. Careful analysis of the distribution of high-momentum untrapped atoms, both from simulations and experiments, shows that the tails of the distribution does not follow a normal law, hinting at a power-law distribution and non-ergodic behavior. We also revisit the phenomenon of décrochage, the potential depth below which the temperature of the atoms starts increasing.

I. INTRODUCTION

Laser cooling in multilevel atomic systems has been a well used technology for the last 25 years; good reviews of its development are given in Refs. [1][2][3][4]. A framework for the theory was developed early on (see, e.g., [5,[START_REF] Castin | Light Induced Kinetic Effects on Atoms, Ions, and Molecules[END_REF] and additional references in [1][2][3][4]), involving coherences and optical pumping between levels in the ground state multiplets. Although these models have provided great insights, and reproduce many important experimental findings, they still fail to explain some experimental results, where finer details of the cooling mechanism and the resulting velocity distributions have been studied.

A laser-cooled atomic sample typically has a steadystate velocity distribution to which a Gaussian function provides a very good fit. This has made it possible to assign "kinetic temperatures" to the ensembles, even though a strict thermal equilibrium does not exist.

When the laser cooling intensity is very low, small but significant deviations from Gaussian distributions have been observed experimentally [START_REF] Jersblad | [END_REF][8][9] and predicted theoretically [10,11]. The experimental observations have been made with dissipative optical lattices [12], or a corresponding laser cooling configuration, and the physical explanation for the observed non-Gaussian distributions has been a contentious point.

A. The interest of laser cooling

The lack of a complete understanding of the cooling mechanisms has not been a major practical problem in cold atom physics, since laser cooling is a technology that does work excellently as a tool. It has been the key to the advent of Bose-Einstein condensation in dilute atomic gases, and is a major ingredient, for example, in experiments with frequency standards, quantum information, and fundamental metrology.

Recently, the interest in fundamental laser cooling has been revived. This is to a large extent due to practical reasons, as scientists are turning towards systems that are increasingly more difficult to laser cool than the alkali atoms that have been the workhorses in most laser cooling related research hitherto (Na, Rb and Cs). As the complexity increases, so does the need for an understanding of how to adapt the technology in order to achieve the desired cooling. One example is molecular laser cooling [13][14][15][16][17], where the presence of vibrational and rotational degrees of freedom typically result in extremely complex energy level diagrams.

In the case of atoms, more complex systems than the staple elements are being studied more closely. Such examples are Li and K (see, e.g., [9,[18][19][20][21][22]), which are alkalis as well, but that have hyperfine structure splittings that complicate the cooling process. Increased knowledge of the laser cooling process may also be required when atoms are cooled in a setting, or geometry, that significantly changes the conditions, or in the cooling of other types of systems (see, e.g., [23][24][25][26][27][28]). With these new challenges to laser cooling, the motivation for deepening the understanding of the cooling process increases, as does the need for honing theoretical and numerical tools for its analysis.

B. Investigating the velocity distribution

In this work, we study the velocity distribution of atoms laser-cooled in a shallow optical lattice in detail, both experimentally and theoretically. In particular, we address the issue of whether, for a shallow optical lattice, the entire atomic population can be adequately described by a single distribution function, and if spatial averaging can be applied, or if the fraction of the atoms that are localized at potential minima has to be accounted for. Thereby, we seek to clarify the impact of localization on observed non-Gaussian momentum profiles. These issues were addressed by some of us already in Ref. [START_REF] Jersblad | [END_REF], with conclusions that have been supported by others [9,29,30]. However, controversies have followed concerning the interpretation of velocity distributions [8,11,[31][32][33], which have motivated us to revisit the question.

II. THEORY

A. The standard model of laser cooling -Sisyphus cooling

When sub-Doppler cooling was first discovered experimentally [34], the theoretical explanation that followed shortly afterwards was based on the concepts of polarization gradients and atomic state degeneracy. Spatiallydependent optical pumping induces slow time scales and a time lag between the internal and external evolution of the atoms. The model is often referred to as Sisyphus cooling [5].

Sisyphus cooling was explained qualitatively by the seminal model of Dalibard and Cohen-Tannoudji [5]. In its most simple form, this model assumes that atoms are moving as classical particles through a one-dimensional modulated optical potential. The latter emanates from two red-detuned laser beams with orthogonal linear polarization -the so-called lin⊥lin configuration.

The key to the cooling mechanism is the internal structure of the atom, coupled to the spatially-alternating polarization of the light. For an atom with a ground-state angular momentum J g = 1/2, there exist two magnetic sublevels M g = ±1/2. The degeneracy of these two states is broken by the AC Stark shift arising from the interaction with the laser-cooling light, in such a way that two sinusoidal potentials, phase-shifted by half a period, are created. Absorption of laser photons followed by spontaneous emission then leads to optical pumping between the two magnetic states. For a correctly chosen detuning of the light, the probability for optical pumping is at its largest at the peak of the a potential, while it is lowest at its bottom. Since the peak of the potential of, e.g., the M g = 1/2 state coincides spatially with the bottom of the M g = -1/2 potential, this will have the consequence that the atom on average spends more time climbing the peaks of the potential than it spends falling down towards its valleys. After averaging over the two internal states, and over a spatial period of the lattice, this therefore leads to an effective friction force. In addition, the fluctuations induced by the randomness of the optical pumping process also lead to diffusion. The balance between friction and momentum diffusion determines the steady-state temperature of the atoms.

This model, albeit simple, appears to capture the essence of the physical mechanism behind Sisyphus cooling. It has been vindicated by good qualitative agreements with more advanced theoretical simulations, as well as with experiments (see, e.g., [35]). For instance, the linear scaling between temperature and potential depth is correctly predicted by this model [36].

However, for a detailed agreement between model and experiments, there are a number of complications which need to be considered, and some unresolved problems. This includes the three-dimensionality of the optical potential, the more complicated level structure of real atoms, the rate of cooling, quantum effects, and taking the full spatial modulation of the atomic densities into account. In the 1990s, there was a considerable effort to enhance the understanding of the cooling mechanisms involved (see, e.g., [37][38][39][40][41][42][43], and other references within those articles). In these works, different theoretical approaches (semi-classical as well as fully quantum mechanical ones) were compared with detailed experiments and important insights were gained. To our knowledge, an extensive review of all hitherto known aspects of polarization-gradient cooling is lacking, and such a treatise is also beyond the scope of the present work. This study is focused on the issue of the shape of the steadystate velocity distribution that arises from the cooling.

The constant friction and diffusion coefficients obtained by the spatial averaging procedure in Ref. [5] entails a perfectly Gaussian momentum distribution of the atoms. While on the whole this profile agrees remarkably well with the majority of the experimental findings, it cannot explain the small deviations in the wings of the momentum distribution found experimentally in, e.g., Refs. [START_REF] Jersblad | [END_REF][8][9]. This is by no means surprising, considering the many simplifications of the theory required to derive the perfectly Gaussian profile, as summarized below. Deviations from Gaussian velocity distributions are also noted in some of the works referenced in the preceding paragraph, as well as Ref. [START_REF] Castin | Les limites du refroidissement laser dans les mélasses optiques à une dimension[END_REF].

Gaussian velocity distribution

Several works describe how the one-dimensional Sisyphus cooling model leads to a Gaussian momentum distribution, see for example Refs. [5-7, 45, 46]. We present here only a brief outline.

The cooling is expressed as a friction force,

F (p) = - αp m . (1)
This is only true within a narrow velocity range, called the velocity capture range (or momentum capture range, p c ), and the assumption is made that the entire sample is within this domain.

The cooling is counterbalanced by a momentum diffusion, D p , which is time-averaged and taken as independent of velocity. D p has two main contributions, (3) In steady-state, for a momentum-independent diffusion D p , the solution of Eq. (3) leads to a Gaussian distribution,

D p (p) = D (ph) p + D (pot) p , (2) with
W (p) t = W 0 exp - αp 2 2m 3 D p . (4)
Below a certain laser intensity, the Sisyphus cooling becomes too weak to retain a normalizable momentum distribution. This means that for weaker laser intensities, the linear scaling of the temperature is broken, and instead the temperature increases rapidly with shallower optical potentials. This has been verified in many experiments, e.g., Refs. [36,47].

The phenomenon that, for intensities below a critical one, the measured temperature quickly increases has often been referred to as décrochage (see, e.g., [START_REF] Hodapp | [END_REF]) [START_REF]The English translation of the French word "décrochage" is "unhooking[END_REF]. In the early literature, this effect was frequently taken as a consequence of the velocity capture range becoming too narrow to catch the entire Boltzmann distribution and thus the sample, the optical molasses, would disintegrate. In this article, we will a priori use the term with its phenomenological definition, and we will discuss its causes in Sec. V.

B. Non-Gaussian velocity tails

A simplification made in Ref. [5] is the assumption that the total density profile of the atoms (summing both magnetic states) is spatially uniform, while the spatial dependence of the two sublevels simply mirror the spatial dependence of the pumping rates between the two states. A first step towards a more complete theory, while retaining most of the conceptual simplicity of the model of Dalibard and Cohen-Tannoudji, is to include also the effect of the motion in the potentials when determining the spatial dependence of the density profiles in the different potentials (while still assuming that the total population has no spatial modulation) [START_REF] Castin | Light Induced Kinetic Effects on Atoms, Ions, and Molecules[END_REF]. In doing this, a momentum dependence is introduced into the populations, and hence into the friction and diffusion coefficients. When this momentum dependence is included, the wings of the atomic momentum distribution change from a Gaussian to a power-law form [START_REF] Castin | Light Induced Kinetic Effects on Atoms, Ions, and Molecules[END_REF]10].

Another consequence is more insight into the existence of a lower limit for the intensity, for which the equilibrium temperature is minimized. This décrochage phenomenon now becomes more directly related to the modulation depth of the optical potentials. As can be expected, the non-Gaussian features observed in the momentum distributions are especially prominent for potential depths close to or below this critical point.

Taking into account momenta beyond p c , the expressions for friction and momentum diffusion have to be replaced by

F (p) = - αp m 1 + p pc 2 (5)
and

D p (p) = D (ph) p + D (pot) p 1 + p pc 2 . (6)

Tsallis distribution

In Ref. [10], Lutz showed that the semi-classical model of Sisyphus cooling presented in Sec. II A leads to a steady-state Wigner function for the momentum distribution of the atoms [see Eq. ( 3)] given by

W q (p) = Z -1 q 1 -β(1 -q)p 2 1/(1-q) , (7)
which is in the form of a Tsallis function [START_REF] Tsallis | [END_REF]. The factor Z -1 q corresponds to an amplitude, and the parameters β and q can be derived from the friction and the diffusion coefficients as

q = 1 + 2m 3 D (ph) p αp 2 c (8)
and

β = α 2m D (ph) p + D (pot) p . (9)
We stress that this momentum distribution is obtained when the possible trapping and localization of atoms in optical lattice sites has been neglected. While a Gaussian is recovered from Eq. ( 7) when q → 0, it leads to the possibility of non-Gaussian velocity distributions, especially in the high-velocity part of those distributions (the "tails") where trapping is no longer relevant. It has also been shown to lead to anomalous diffusion [46,50] in the optical lattice. We note that even in the case where some atoms are trapped, Eq. ( 7) may still be a good description for a part of the atomic population that remains untrapped.

C. Localization at lattice sites

The model using momentum-dependent friction and diffusion in Ref. [START_REF] Castin | Light Induced Kinetic Effects on Atoms, Ions, and Molecules[END_REF] goes some way to include the effects of the modulation of the potential on the atomic populations. However, it still assumes that the total atomic population is spatially uniform, and employs spatial averaging over a period of the lattice. In the limit of atomic energies (kinetic+potential) smaller than the depth of the lattice, the atoms will localize near the bottom of the potential wells. As the regions close to the peaks of the lattice will be inaccessible to these atoms (independently of their internal state), it is clear that the assumption of a spatially uniform total atomic distribution will not hold. This localization effect has been theoretically and experimentally verified in deep optical lattices [51][52][53][54][55][56][57]. It is, however, less clear if localization plays an important role in lattices where the momentum profile of the atoms have prominent non-Gaussian wings, i.e., at or below dérochage.

With the presence of the optical lattice light, there will always be heating present, with the possibility for a trapped atom to become untrapped. This untrapped atom will in turn be exposed to laser cooling. Thus, we assume that at any given time, a subset of the atomic population will be moving across the lattice, whereas another portion of atoms will be localized. Moreover, there will be transfers between these two populations and a corresponding steady state (provided no atom can escape from the optical lattice). For deep optical lattices, the portion of untrapped atoms will be very smalltypically too small to measure. For very shallow lattices however -close to décrochage -there will be significant portion of both classes of atoms, and thus a snapshot of the velocity distribution should show a bimodal distribution. Under the assumption above, the untrapped atoms ought to follow a power-law distribution, as in Eq. ( 7), whereas the trapped portion should be fitted separately, for example to a truncated Gaussian.

III. SEMI-CLASSICAL SIMULATIONS A. Numerical methods

We calculate the steady state of atoms in a onedimensional optical lattice using the semi-classical method described in Refs. [START_REF] Castin | Light Induced Kinetic Effects on Atoms, Ions, and Molecules[END_REF][58][59][60]. While the lattice is 1D and only motion along the lattice axis is considered, photons can be spontaneously emitted in any direction in 3D. The position and momentum are treated as classical variables, described by a Wigner distribution, while a quantum representation is used for the internal state of the atom. We consider two cases for the latter: either a J g = 1/2 ↔ J e = 3/2 transition, the minimal degeneracy exhibiting Sisyphus cooling, or the F g = 4 ↔ F e = 5 transition corresponding to cesium cooled on the D2 line, including the presence of the F e = 4 state [60]. In the first case, the laser does not couple the two ground states (an atom only shifts between them through spontaneous emission), such that an atom is found in either of the ±1/2 substates at any given time. In the other case, the atoms end up in superpositions of either even or odd M F substates (adiabatic potentials).

The simulations depend on two parameters: the detuning ∆ of the laser with respect to the atomic transition and ∆ ≡ ∆s 0 /2, with s 0 the saturation parameter [61]. The former is usually expressed in units of the natural linewidth of the excited state, Γ, while the latter is directly proportional to the amplitude of the optical lattice potential. The potential depth is given by

U = A |∆ | , (10)
where A = 2/3 for the 1/2 ↔ 3/2 transition and A = 4/9 (based on the lowest adiabatic potential) for the 4 ↔ 5 transition. Energies are conveniently expressed in terms of the recoil energy,

E rec ≡ p 2 rec 2m , (11)
i.e., the kinetic energy gained by the atom when spontaneously emitting a photon, where p rec ≡ k, with k the wave vector of the optical lattice laser.

Unless otherwise noted, the results are obtained for 200000 and 100000 independent atoms for the 1/2 ↔ 3/2 and 4 ↔ 5 transitions, respectively. Momentum distributions along the axis of the optical lattice are obtained by accumulating the final momentum of atoms into bins of width p rec .

To determine if an atom is trapped or not in one of the potential wells of the lattice, we need to compare its total (potential+kinetic) energy with the depth of these potential wells, Eq. (10). This is straightforward for the 1/2 ↔ 3/2 case, where the amplitude U of the potential is the same for both internal states. For the 4 ↔ 5 transition, the light shift varies with the M F substate [12] and an atom is found in a superposition of M F states, with optical pumping pushing atoms towards the extreme M F = ±F states [62]. Moreover, we find that the adiabatic potentials [12] better represent the interaction of the atom with the laser field. Therefore, for the 4 ↔ 5 transition, we define as trapped atoms that have an energy lower than the barrier height in the lowest adiabatic potential. This results in a slight overestimation of the number of trapped atoms in this case, as some atoms that are not in the lowest adiabatic state can be counted as trapped even though they have enough energy to escape to a neighboring well in another adiabatic state.

We can calculate the maximum momentum p trap an atom can have and still be trapped as

p trap p rec ≡ U E rec 1/2 = A |∆| E rec 1/2 . ( 12
)
Note that an atom with a momentum 0 ≤ p ≤ p trap can either be trapped or untrapped, depending on the amount of potential energy it has at its current position and state.

B. Numerical results

Trapped vs. untrapped atoms

We show in Fig. 1(a) a typical momentum distribution for the 1/2 → 3/2 transition, for all atoms taken together and for trapped and "free" (untrapped) atoms separately (see Sec. III A for a definition of those terms). The central core of the distribution, around p/p rec = 0, is mostly made up of trapped atoms, while the tails of the momentum distribution are due to untrapped atoms. Apart from a small transition region, trapped and untrapped atoms are found at different values of the momentum. Obviously, no trapped atom can have p > p trap , but we also find that few untrapped atoms have a momentum p ∼ 0. This separation in momentum of trapped and untrapped atoms reinforces the conclusions of Refs. [START_REF] Jersblad | [END_REF]63], where experimental results and quantum simulations of the dynamics of the cooling indicated the presence of "cold" and "hot" modes in the momentum distribution.

Plotting the same data on a log scale [Fig. 1(b)] the distribution of trapped atom appears as an inverted parabola, cutoff at p trap /p rec ≈ 5.78 [see Eq. ( 12)]. Indeed, the fit to a Gaussian function is very good, as seen in Fig. 1(c). However, the tails of the total momentum distribution, corresponding to untrapped atoms, do not appear to follow a Gaussian function.

To check this further, we fit the full data of Fig. 1 to different functional forms, namely a single Gaussian, a Tsallis function Eq. ( 7), and two Gaussian functions, see Fig. 2. While both the Tsallis function and the double Gaussian reproduce quite well the core of the distribution, this is at the detriment of the tails. Fitting the entire dsitribution to a sum of a Gaussian and a power-law function, or to a Gaussian and a Tsallis function, gives an excellent fit. However, this means a function with so much liberty, and so many free parameters, that it is highly questionable if any pertinent conclusion can be drawn from such a fit. Moreover, a power-law function has to be truncated at some point. Instead, we find a fit to a double Gaussian a better indication that the distribution consists of two distict energy modes. In order to test the functional form of the tails of the distribution, a more stringent test is to fit the highmomentum part of the distribution separately. We will address this point in more detail below in Sec. III B 2.

Similar results are obtained when considering the level structure for the F g = 4 → F e = 5 transition in cesium, Fig. 3, whether including one (F e = 5) or two (F e = 4, 5) excited states in the simulation. Calculating the root-mean-square value of the momentum p rms , we find that the 4 → 5 transition leads to a lower temperature (p rms /p rec = 7.52) compared to the 1/2 → 3/2 transition (p rms /p rec = 9.54), for the same choice of parameters (∆ = -10Γ and ∆ = 50E rec / ). There is also stronger trapping for the 4 → 5 transition, with 71.6% trapped atoms, compared to 65.0% for the 1/2 → 3/2 transition. (This may be due to an overestimation in the former case, see Sec. III A.)

Power-law tails

It was shown in Ref. [10] that, when neglecting the spatial modulation of the optical lattice and thus the possibility of trapping, the momentum distribution of atoms is in the form of a Tsallis function [START_REF] Tsallis | [END_REF]. Considering only untrapped atoms, this calculation predicts for a 1/2 → 3/2 transition a tail of the distribution of the form

W (p) = N 1 + 90 41 ∆ 2 Γ 2 + p 2 p 2 c
15pc(∆/Γ)/41 (13) with p c = Γs 0 /(36E rec ) and N a scaling constant. We present in Fig. 4 the data for the tails of the momentum distribution for the 1/2 ↔ 3/2 transition with ∆ = -10Γ and |∆ | = 50E rec / (same as in Fig. 1). We have combined here the data points for both negative and positive momenta. We have fitted the data for the tail separately, selecting the part of the distribution with |p| /p rec ≥ 10, with Eq. ( 13), using N as the only free parameter, as p c can be expressed in terms of the simulation parameters ∆ and ∆ . The result (full line in Fig. 4) agrees very well with the simulated data, especially for smaller values of the momentum (the statistics get worse as the momentum increases, as very few atoms reach high momenta in the simulation). For comparison, we have also fitted the tail to a Gaussian function (dashed line in Fig. 4), and the result clearly shows that the momentum of untrapped atoms does not follow a normal distribution. This would indicate that the system is non-ergodic [64].

While the theory presented in Sec. II B appears to work well for untrapped atoms, the bimodal nature of the distribution argues against the use of a single function to describe the entire momentum distribution, it appears that a good fit of the core of the distribution results in an incorrect description of the tail, see Fig. 2. It is clear that a double Gaussian function cannot capture all properties of the distribution, but nevertheless it does capture the bimodality, and it does provide a better fit than the Tsallis function, when the entire population is included in the fit.

IV. EXPERIMENTS

In order to further investigate the velocity distribution, we perform an experiment with a three-dimensional optical lattice. The experimental set-up has been described in detail elsewhere (e.g., in Ref. [65]), and therefore the present description is kept brief.

A cold sample of atoms is prepared by stopping a thermal beam of cesium, followed by the loading of the atoms in a magneto-optical trap (MOT). The atoms are then progressively cooled by going through stages of a low-intensity MOT, a low-intensity optical molasses, and eventually the atoms are loaded in a three-dimensional dissipative optical lattice. This traps the upper hyperfine structure state of the ground configuration, 6s 2 S 1/2 , F g = 4.

The optical lattice configuration is shown in Fig. 5. Four laser beams with identical detunings and intensities make an angle of π/4 with the principal axis (ẑ), with the latter being parallel to the vertical axis. Two beams are in the xz-plane and are polarized along ŷ, whereas the other two are polarized along x and propagate in the yz-plane. The lasers are typically detuned by ∆ = -25Γ from the resonance F g = 4 ↔ F e = 5 in the D2 line of Cs (see, e.g., [START_REF] Steck | Cesium D line data[END_REF]), at λ ≈ 852 nm, but this may be varied. That is, the light-atom interaction is in a regime where the kinetics of the atoms are strongly influenced by incoherent scattering, which includes both laser cooling and momentum diffusion.

The resulting optical lattice potential is illustrated in Fig. 6 (the lowest adiabatic potential is shown). Along the vertical ẑ-axis, we have a sinusoidal potential, and a cooling configuration that closely corresponds to the one-dimensional lin⊥lin configuration, and thus also to the model used in Sec. III. The potential depth scales proportionally to I/∆ (see eq. 10), with I the laser irradiance, and is thus tunable.

The velocity distributions are observed by using the time-of-flight method [65], where atoms are released from the optical lattice and are allowed to expand under free fall. The expansion is then measured by a laser probe. In our experiments, we obtain a signal-to-noise ratio in the measured velocity distributions better than 1:1000 (in a single shot), and a velocity resolution better than 10 nK. The maximum repetition rate is of the order of one hertz, and thus, good statistics can easily be obtained.

A. Experimental results

The velocity distribution has been recorded for a range of potential depths. In Fig. 7 we show a result, for the case of very low intensity, and hence very shallow lightshift potentials (U/E rec = 106, obtained for a laser power of P = 0.13 mW per beam). As has been previously shown (see, e.g., [START_REF] Jersblad | [END_REF]47,68]) a fit to a Gaussian function of the velocity distribution gives an estimate of the kinetic temperature of the sample, and above a certain critical potential depth -of the order of 10-100E rec -the temperature scales linearly with potential depth (I/∆). FIG. 7. (Color online) Velocity distribution recorded for a shallow optical lattice (U = 106Erec), close to the critical potential depth (average of two measurements). In the full figure, the dotted green line is a Gaussian function fitted to the data. Fits to a Tsallis function, or to a double Gaussian, are visually indistinguishable from the experimental data at this scale, and are therefore not included. In the inset is a zoom-in of the wing of the distribution. The dotted green line is still the single Gaussian, whereas the dashed blue line is a fit to a Tsallis function, and the full red line one to a double Gaussian. The same data as in Fig. 7, but shown in a logarithmic scale. The mismatches of the fits, as quantified by their χ 2 -values are: χ 2 = 0.16 for a single Gaussian (dotted green line), χ 2 = 0.0068 for a Tsallis function (dashed blue line), and χ 2 = 0.011 for a double Gaussian (full red line). For all fits, the y-intercept is a fitting parameter, which explains why the fits flatten out. The influence of this on the least-squares fit is negligible, since it concerns data three decades smaller than the center of the distribution.

For deep potentials, Gaussian fits to the velocity distributions are excellent. Close to the critical point (as in Fig. 7), such fits are still fairly good, but there is a systematic underestimation of the wings of the distribution. There is a high-velocity tail that cannot be mimicked by a Maxwell-Boltzmann distribution.

In Fig. 7 -and also in Fig. 8, which is the same data plotted in a logarithmic scale -we show fits of various functions to the data. A Tsallis function gives a good fit, and so does a double Gaussian. However, when the Tsallis function is fitted to the entire distribution, it gives systematicalle different fit results than it does when only the high-velocity tail is fitted. The double Gaussian is just the simplest bimodal model, and it is noteworthy that it still provides as good a fit as does the Tsallis function.

The results supports the assumption that a significant part of the atomic population is localized in optical lattice sites. For deep lattices, this proportion is close to 100%. Closer to the critical point, a gradually larger proportion of the atoms will, on average, be untrapped, and therefore analyzing the entire population in terms of one single distribution function will not give a fully pertinent description. This is totally consistent with the numerical results in Sec. III and with experimental results reported by others in, e.g., Refs. [9,51].

V. DISCUSSIONS

The observation that the atoms are found in two modes, trapped and untrapped, allows us to revisit a striking feature of laser cooling by optical lattices, the décrochage mentioned in Sec. II B. This phenomenon can be seen in Fig. 9, where the root-mean-square momentum p rms obtained from the numerical simulations is plotted as a function of ∆ , which is directly proportional to the potential depth. It now appears that only untrapped atoms are responsible for the décrochage phenomenon observed in an experiment. While the value of p rms of the trapped atoms varies monotonously with ∆ , the momentum of untrapped atoms increases as the potential depth goes below the threshold of décrochage. This effect is magnified by the fact that the proportion of trapped atoms is significantly reduced for shallow potentials, as seen in Fig. 10. We notice the greater trapping of atoms with a higher degeneracy of the ground state. We also point out that a significant portion of the atoms remain trapped even past décrochage, and that it is only for extremely shallow potentials that the majority of atoms are not trapped. In an experiment, the average of all atoms will be measured, and even though few atoms are untrapped, the very high momentum of these will give rise to the observed "unhooking" (departure) of the recorded data from the linear intensity dependence.

Two additional remarks on Fig. 9 are in order. First, for a two-level system (1/2 ↔ 3/2 transition) there is only a slight influence of the detuning ∆ on the values of p rms obtained, with higher values obtained for smaller detunings, at a given value of ∆ . Within the range ∆ = -10Γ to -30Γ, the values do not differ by more than the statistical noise of the simulations. However, a difference becomes clear at ∆ = -5Γ, while the values at -2Γ stand out even at the scale of the figures presented here. We find a similar result when we consider the 4 ↔ 5 transition without the presence of the F e = 4 state (see also [69]). This is not the case for the three-level 4 ↔ 5 transition (i.e., with the F e = 4 state included), Fig. 9(b), where the position of décrochage is clearly influenced by the detuning, as previously noted in Ref. [60]. This is in agreement with experimental results for both cesium [47] and rubidium [70], where it was found that décrochage appears at constant laser irradiance (meaning constant s 0 in our model, so that the potential depth becomes di-rectly proportional to the detuning ∆). This dependence on the detuning is also reflected in the fraction of trapped atoms, see Fig. 10.

For full disclosure all data used for the figures in this article are published in Ref. [71], in order to enable further analysis by others.

VI. CONCLUSIONS

Our results, both experimental and numerical, strongly support the assumption that the velocity distribution of atoms trapped in a shallow, dissipative optical lattice is bimodal. We have found nothing that supports an hypothesis that at some potential depth, near décrochage, there is a sudden transition between a localized regime and a jumping one. Rather, our data supports the theory that atoms that are constantly exposed to both laser cooling and heating in a dissipative optical lattice go through periods of being trapped as well as of being untrapped. At any given moment, the entire population will consist of these two modes.

For deep optical lattices, the untrapped portion will be very small. Closer to décrochage (i.e., for decreasing potential depth) a gradually larger subset of the ensemble will have enough energy to move over more than one lattice site. For these shallow potentials, a fit to a single distribution function of the entire population cannot be adequately applied, and any theory that applies spatial averaging of the atomic density, over several lattice sites, will fail to account for the significant portion of the atoms that remain trapped.

For the untrapped atoms, a power-law distribution such as Eq. ( 7) gives a good fit to numerical data. Also for the experimental data, the high-velocity tail of the distribution clearly deviates from a simple Gaussian, but it is more difficult to prove a power-law distribution. For a detailed experimental study of a sample displaying non Boltzmann-Gibbs statistics, as suggested in, e.g., Refs. [32,33,64], a different physical system than a pure dissipative optical lattice would be needed. This could for example be a weak Sisyphus cooling configuration superimposed on an external potential. In that case, trapping could be avoided, and spatial averaging can be applied in the analysis. Examples of this is a cooling inside an ion trap, as in Ref. [50], or weak cooling in an external optical trap, as in Ref. [72].

FIG. 1 .

 1 FIG. 1. (Color online) Simulated momentum distribution of atoms cooled on a 1/2 ↔ 3/2 transition in an optical lattice, for ∆ = -10Γ and |∆ | = 50Erec/ . (a) Total distribution (full black line), trapped (blue +), and untrapped (red ×) atoms. (b) Same as (a), but in log scale. (c) Trapped atoms (+) and fit to a Gaussian curve (full line).

FIG. 2 .

 2 FIG. 2. (Color online) Fits to the entire simulated momentum distribution of atoms cooled on a 1/2 ↔ 3/2 transition in an optical lattice, for ∆ = -10Γ and |∆ | = 50Erec/ . Panel (b) is a zoom-in of the data shown in panel (a).In both panels, the simulated data is indicated by crosses, with fits to a single Gaussian (dotted green line), a Tsallis (dashed blue line), and a double Gaussian (full red line) functions. χ 2 values for the fits are 7.1 × 10 -4 , 1.0 × 10 -4 , and 2.7 × 10 -5 , respectively.

FIG. 3 .

 3 FIG. 3. (Color online) Simulated momentum distribution of atoms cooled on a 4 ↔ 5 transition in an optical lattice, for ∆ = -10Γ and |∆ | = 50Erec/ , shown on a logarithmic scale. Total distribution (full black line), trapped (blue +), and untrapped (red ×) atoms; including (a) a single (Fe = 5) excited state; (b) two (Fe = 4, 5) excited states.

FIG. 4 .

 4 FIG. 4. (Color online) Simulated tails (×) of the momentum distribution shown in Fig. 1, for the 1/2 → 3/2 transition (∆ = -10Γ, |∆ | = 50Erec/ ), with fits to Eq. (13) (full line) and to a Gaussian (dashed line).

FIG. 5

 5 FIG. 5. (Color online) Configuration of the three-dimensional optical lattice. A red-detuned beam is split into four beams. These are aligned, and their polarizations are chosen, as shown in the figure. This provides a three-dimensional generalization of the one-dimensional lin⊥lin laser cooling configuration.

FIG. 8 .

 8 FIG. 8. (Color online)The same data as in Fig.7, but shown in a logarithmic scale. The mismatches of the fits, as quantified by their χ 2 -values are: χ 2 = 0.16 for a single Gaussian (dotted green line), χ 2 = 0.0068 for a Tsallis function (dashed blue line), and χ 2 = 0.011 for a double Gaussian (full red line). For all fits, the y-intercept is a fitting parameter, which explains why the fits flatten out. The influence of this on the least-squares fit is negligible, since it concerns data three decades smaller than the center of the distribution.

FIG. 9 .

 9 FIG. 9. (Color online) Root-mean-square momentum for all atoms (filled symbols); and for trapped (blue open symbols, lower points) and untrapped (red open symbols, upper points) only. (a) 1/2 ↔ 3/2 transition (simulations done for 50000 atoms); (b) 4 ↔ 5 transition (simulations done for 5000 atoms).

5 Δ

 5 FIG. 10. (Color online) Fraction of trapped atoms, for 1/2 ↔ 3/2 (filled symbols) and 4 ↔ 5 (open symbols) transitions (simulations done for 50000 and 5000 atoms, respectively).

  D

	instantaneous potential felt by an atom. The competi-
	tion between cooling and heating can then in turn be
	described by a Fokker-Planck equation,
	∂W (p, t) ∂t	= -	∂ ∂p	[F (p)W (p, t)] +	∂ ∂p	D(p)	∂W (p, t) ∂p	.
								(ph) p	arising from the stochastic nature of light
								scattering and D	(pot) p	originating from fluctuations in the

ACKNOWLEDGMENTS

We thank R. Kaiser and L. Sanchez-Palencia for stimulating discussions. This research was funded in part by the Swedish Research Council (VR). The computations were performed on resources provided by the Swedish National Infrastructure for Computing (SNIC) at the National Supercomputer Centre (Linköping University).