Florian Benavent

Bruno Zanuttini

An Experimental Study of Advice in Sequential Decision-Making under Uncertainty

We consider sequential decision making problems under uncertainty, in which a user has a general idea of the task to achieve, and gives advice to an agent in charge of computing an optimal policy. Many different notions of advice have been proposed in somewhat different settings, especially in the field of inverse reinforcement learning and for resolution of Markov Decision Problems with Imprecise Rewards. Two key questions are whether the advice required by a specific method is natural for the user to give, and how much advice is needed for the agent to compute a good policy, as evaluated by the user. We give a unified view of a number of proposals made in the literature, and propose a new notion of advice, which corresponds to a user telling why she would take a given action in a given state. For all these notions, we discuss their naturalness for a user and the integration of advice. We then report on an experimental study of the amount of advice needed for the agent to compute a good policy. Our study shows in particular that continual interaction between the user and the agent is worthwhile, and sheds light on the pros and cons of each type of advice.

Introduction

We consider sequential decision making under uncertainty, by an autonomous agent solving tasks on behalf of a user. Such situations arise naturally in practice, for instance, GPS navigation devices compute optimal routes for the driver. We are especially interested in applications where the agent has information about the dynamics of the task to achieve, but lacks information about the precise goal, or preferences, of the user. In the case of a GPS, this corresponds to the device having all information about the roads and traffic (dynamics) and some information about the goal (starting place and destination), but lacking information about whether the driver wants to, e.g., avoid going though such place, or keep close to others (like rest areas when driving with young kids). We refer the reader to [START_REF] Azaria | Strategic advice provision in repeated human-agent interactions[END_REF] for more examples.

We assume that the task to be solved is modelled as a Markov Decision Problem (MDP), thus taking into account uncertainty in the outcome of actions at execution time. In that setting, natural solutions are policies rather than plans. In the GPS example, this means that the device computes a contingent plan taking into account, not only the intended, optimal path to destination, but also alternative paths (because of, e.g., unforeseen traffic jams, blocked roads, etc.).

It is well-known that the optimal policy for a given MDP is highly dependent on the precise reward function. However, it is typically difficult for a user to give precise numerical values for rewarding states or transitions between states. Hence many authors have studied MDPs with Imprecise Reward functions, that is, with a set of candidate reward functions rather than a single one. Approaches encompass inverse reinforcement learning and learning from demonstrations, preference-based reinforcement learning, ordinal reward MDPs, minimax regret policies, etc. (see related work).

At the heart of most approaches is some notion of information communicated by the user to the agent: demonstrated (portions of) trajectories, preferences between trajectories, etc. Such information can be obtained by observing the user, or by actively querying her whenever more information is needed for solving the task. Orthogonally, the information can consist of (near-)optimal actions to take at given states, to information about the real reward function, etc.

We are interested in what information is given by the user to the agent, which we call advice. We give a unified view of the most important notions in the literature, focusing on notions which, we argue, are natural for a user to give. We introduce a new, natural notion, formalising a user giving the action to take in a given state and telling what outcome made her choose this action. We extend known algorithms for incorporating such advice in the computation of a minimax regret policy. We finally report on an experimental study on random MDPs with different structures, in which we compare the various notions with different interaction scenarios.

Related Work

It has long been observed that a drawback of MDPs, as a framework for modelling sequential decision making tasks, is that a numerical reward function must be defined, and that the optimal policies are quite sensitive to its precise values. A typical setting where this is problematic is in medical decision support, where one would need to give a numerical cost to the death of a patient, implying possible tradeoffs with many other being cured of a simple cold, for instance. The point is that under very reasonable postulates, there is indeed a numerical reward function which captures exactly the task which the user has in mind [START_REF] Weng | Ordinal decision models for Markov decision processes[END_REF]), but that it is not realistic to expect the user to know it.

To cope with this, a first line of approaches considers or-dinal [START_REF] Weng | Ordinal decision models for Markov decision processes[END_REF], or preference-based MDPs [START_REF] Fürnkranz | Preference-based reinforcement learning: a formal framework and a policy iteration algorithm[END_REF], in which rewards or trajectories are ordered but have no numerical values. This results in MDPs with several nondominated policies. For choosing one, methods have been proposed that ask the user the minimum amount of additional information about how rewards compare and can be traded off with each other, either in an offline planning [START_REF] Weng | Interactive value iteration for Markov decision processes with unknown rewards[END_REF] or in a reinforcement learning setting [START_REF] Busa-Fekete | Preference-based evolutionary direct policy search[END_REF]). This information is typically obtained as answers to queries asked to the user. Another group of approaches consists of considering the problem as one of inverse reinforcement learning [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF]. In this setting, the dynamics of the problem is known to the agent but the reward function is considered as an unknown, the value of which (or enough information about this value) can be discovered by the agent by observing optimal or near-optimal policies. Some approaches, called model-based, aim at estimating the underlying reward function first and then deducing an optimal policy, while other, called direct or model-free, aim at computing an optimal policy directly from the demonstrations. We refer the reader to [START_REF] Piot | Learning from demonstrations: Is it worth estimating a reward function?[END_REF] for a recent survey.

Finally, another (closely related) group of approaches takes a decision-theoretic point of view, and defines an Imprecise Reward MDP (IRMDP) to be a set of MDPs, all with a different reward function, hence modelling uncertainty about the real one. Different solution concepts can be given, but the one most studied is minimax regret [START_REF] Bell | Regret in decision making under uncertainty[END_REF][START_REF] Xu | Parametric regret in uncertain Markov decision processes[END_REF][START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF]. With this view, ignorance of the real reward function is directly coped with, and an optimal policy is one which copes best with it: in the case of minimax regret, which is most robust to adversaries choosing the real reward function. This line of work also studies methods for reducing the uncertainty using queries to the user, as far as needed for reducing regret [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF][START_REF] Weng | Markov decision processes with ordinal rewards: reference point-based preferences[END_REF][START_REF] Alizadeh | Approximate regret based elicitation in Markov decision process[END_REF][START_REF] Ahmed | Sampling based approaches for minimizing regret in uncertain Markov decision processes (MDPs)[END_REF]. In this paper, we heavily build on this view and these techniques.

Preliminaries

A Markov Decision Problem, or MDP [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF], is a tuple S, A, T, R, γ , where: S, A are finite sets of states and actions; T : S × A × S → [0, 1] is a transition function, with T (s, a, s ) the probability that when action a is taken in state s, the system evolves to state s ; R : S → R is the reward function, with R(s) the immediate reward (or penalty, if negative) obtained when the current state is s; and γ ∈ [0, 1[ is the discount factor. 1 Write ∆(X) for the set of all probability distributions over a set X. The transition function T is made of one probability distribution for each state s and action a, written T s,a ∈ ∆(S). A (stationary) deterministic policy is a function π : S → A, which for each state s prescribes an action a to take, and more generally a (stationary) stochastic policy is a function π : S → ∆(A); we write π(s, a) for π(s)(a), that is, for the probability that a is chosen in state s according to π. We write f α π for the occupation frequency of π wrt an 1 Our study can be easily generalised to R :

S × A × S → R initial distribution α on S: f α π (s, a) = E( ∞ t=0 γ t Pr(S t = s, A t = a))
, where expectation is taken over trajectories defined by S 0 ∼ α, A t ∼ π(S t ), and S t+1 ∼ T St,At .

In this paper, we define the quality of policies respective to the infinite horizon discounted criterion: the value of π at a state s is defined to be the expectation of cumulative discounted rewards obtained when following π starting in s:

V π (s) = E( ∞ t=0 γ t R(S t ))
where S t is a random variable on S for t = 0, 1, . . . , and expectation is taken over trajectories defined by S 0 = s, A t ∼ π(S t ), S t+1 ∼ T St,At . The quality function is given by

Q π (s, a) = R(s) + γ s ∈S T (s, a, s )V π (s )
It is well-known that an MDP M always has an optimal deterministic, stationary policy π which maximises V π (s) at all states s. We denote by π * M such a policy, by V * M : S → R its value function, and by

Q * M : S × A → R its Q-function.
Imprecise Reward MDPs We adopt the setting of Imprecise Reward MDPs (IRMDPs). Formally, an IRMDP [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF]) is defined to be a tuple S, A, T, R, γ , where S, A, T, γ are as for an MDP, and R is a (possibly infinite) set of reward functions on S; R models the uncertainty about the real reward function which would precisely define the task at hand. To avoid confusion, we use notation M for IRMDPs, keeping M for (standard) MDPs. We are interested in the case when R is given as a polytope. Precisely, writing S = {s 1 , . . . , s n } for the set of states, we assume that R is the set of all solutions of a linear system of the form C • r ≥ d, where C is a k × n-matrix, d is a k-dimensional column vector, and r is the column vector (R(s 1 ), . . . , R(s n )) T . We call such IRMDPs linear.

The restriction to linear IRMDPs is very common in the literature [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF]2010;[START_REF] Weng | Interactive value iteration for Markov decision processes with unknown rewards[END_REF][START_REF] Alizadeh | Approximate regret based elicitation in Markov decision process[END_REF][START_REF] Ahmed | Sampling based approaches for minimizing regret in uncertain Markov decision processes (MDPs)[END_REF]. It is indeed very natural; in particular, it encompasses all cases where the modeller of the task specifies an interval instead of a precise value for some R(s)'s.

Solving IRMDPs [START_REF] Xu | Parametric regret in uncertain Markov decision processes[END_REF] and [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF] propose to assess the value of a stochastic policy for an IRMDP using max regret (MR). The intuition is that a good policy should not bet too much on one of the reward functions, and should rather try to minimise its regret if an adversary chooses the actual one.

Definition 1 (max regret) Let M = S, A, T, R, γ be an IRMDP, π be a stochastic policy, and α be a distribution on S. For R ∈ R, the regret of π wrt M and R is defined by

ρ α M (π, R) = max g∈Fα (R • g -R • f α π )
, where F α is the set of all valid action occupation frequencies for M wrt α. The max regret of π is defined by

MR α M (π) = max R∈ R ρ α M (π, R). 2 min π,ρ ρ s.t. R • g R -R • f ≤ ρ (∀ g R , R ∈ R) γE T f + α = 0 max Q,V,I,r α • V -r • f s.t. Q a = r a + γP a V (∀a ∈ A) V ≥ Q a (∀a ∈ A) V ≤ (1 -I a )M a + Q a (∀a ∈ A) Cr ≤ d a I a = 1 I a ∈ {0, 1} M a ∈ M -M ⊥ a Figure 1: Master problem (top) and subproblem (bottom) for M = S, A, T, R, γ with R given by C • r ≥ d.
When unambiguous, we simply write ρ(π, R), MR(π). A policy π * is said to be MMR-optimal (for M ) if its max regret is minimum:

MR α M (π * ) = min π∈(∆(A)) S MR α M (π).
Several algorithms have been proposed for computing an MMR-optimal policy [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF][START_REF] Da Silva | A geometric approach to find nondominated policies to imprecise reward MDPs[END_REF][START_REF] Alizadeh | Solving MDPs with unknown rewards using nondominated vectorvalued functions[END_REF], either exactly or approximately. Among these, we will build on Regan and Boutilier's approach (2009). Given an IR-MDP M = S, A, T, R, γ with R given by a linear system C • r ≥ d, the idea is to use Bender's Decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]. A master problem computes a policy which minimises the maximal regret with respect to the reward functions in a finite subset R of R. Given such a candidate policy π, a subproblem searches for a reward function R ∈ R which maximises the regret of π, R is added to R, and the process repeats until a fix-point is reached. It turns out that the master problem can be formulated as a linear program over variables f (s, a) ∈ [0, 1] (s ∈ S, a ∈ A, representing the occupation frequency of an MMR policy) and ρ (representing the min max regret). Figure 1 (top) gives this program. The first constraint occurs once per couple g R , R which has been found by the subproblem so far, where R is a regret maximising reward function as found by the subproblem, and g R is the occupation frequency of the corresponding adversary policy. The second constraint ensures that f is a valid occupation frequency (for α). A solution policy can be retrieved from f through π(s, a) = f (s, a)/ a f (s, a ). Now, the subproblem can be formulated as a mixed 0/1 linear program as shown on Figure 1 (bottom). There, f is the occupation of the current MMR solution π found by the master problem, r is a vector of realvalued variables representing a reward function for which ρ(π, r) is maximal, Q, V are vectors of real-valued variables representing the quality function and value function of a deterministic policy π g maximising r • g -r • f (with g the occupation function of π g wrt α) or, equivalently, α • V -r • f , and [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF] for more details).

I consists of 0/1 variables such that I a (s) is 1 iff π g (s) is a (cf.

Max Regret under Advice

We consider agents who know the dynamics (S, A, T, γ) of the target MDP, but know a set R instead of the reward function R. However, we consider situations where there is a precise task to be solved, as formalised by a precise numerical reward function R. This function must be understood as the one in the user's mind, but we insist that we do not assume that the user knows it precisely. Note that, under reasonable postulates, there is necessarily such a function which models the user's preferences (Weng 2011, Theorem 2).

We call advice context a tuple S, A, T, R, γ, R , where S, A, T, R, γ is an IRMDP and R ∈ R is a reward function over S: S, A, T, R, γ is the information available to the agent, and the MDP M = S, A, T, R, γ is the target task.

Advice In general, by advice we formalise the hints a user can give to the agent about the target reward function. Hence we view a piece of advice as a predicate on reward functions.

A natural manner for a user to give advice about the precise task at hand, is to point at decisions which she would take in specific states. This is the point of view taken by learning from demonstrations [START_REF] Maclin | Creating advice-taking reinforcement learners[END_REF][START_REF] Judah | Reinforcement learning via practice and critique advice[END_REF][START_REF] Azaria | Strategic advice provision in repeated human-agent interactions[END_REF][START_REF] Cederborg | Policy shaping with human teachers[END_REF]. Importantly, giving such advice does not require the user to know anything about the components of the target task. Rather, the agent can simply run its MMR policy (for M ) until the user says "here, you should have done that".

Definition 2 (action advice) Let S, A, T, R, γ, R be an advice context, write π * for an optimal policy for M = S, A, T, R, γ , and π * for an MMR policy for M = S, A, T, R, γ . An action advice is a pair (s, a)

∈ S × A satisfying Q M π * (s, a) ≥ Q M π * (s, π * (s)
). We emphasise that in Definition 2, the Q-values are all evaluated in the target model M and assuming that the policy executed after them is the target policy π * . Hence the advice indeed makes sense, in that it does not require the user to know the agent's model.

Another natural type of advice is about the optimal action in a given state, still according to the user's point of view.

Definition 3 (optimal action advice) Let S, A, T, R, γ be an MDP, and π * be an optimal policy for it. An optimal action advice is a pair (s, a) ∈ S × A satisfying a = π * (s).

Again, such advice does not require the user to know the agent's model. From the point of view of the agent, the informative content of such advice is

∀a ∈ A, s ∈S T (s, a, s )V M π * (s ) ≥ s ∈S T (s, a , s )V M π * (s )
Because the inequality is large, such advice may be noninformative, which is reminiscent of the fact that the basic inverse reinforcement learning problem is ill-posed [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF]. However, contrary to (nonoptimal) action advice, such advice does not require the user to know the agent's policy. Dually, nonoptimal action advice requires this, but does not require her to know the optimal action in the target MDP. Hence it makes sense for complex tasks for which the optimal action is not clear to the user. Action advice is a direct notion of advice. However, in many natural situations we can expect a human user to consider such decisions with a precise outcome in mind. For instance, when deciding to play or not to play a lottery, we can expect a user to focus on the outcomes of winning the jackpot, of not winning anything, but less likely to take into account the probability of second-rank gains or the probability of being hit by a car when walking for buying a ticket.

For that reason, we introduce new notions of advice, in which the user specifies a successor s ∈ T (s, a) of (s, a) in addition to the action advice (s, a). This is obviously always at least as demanding to her as giving only an advice (s, a), but it is natural in many situations, as we argue below.

In general, (optimal) successor advice will consist of a triple (s, a, s ) with (s, a) an (optimal) action advice and T (s, a, s ) = 0. A natural choice for s is a most probable outcome (s ∈ argmax s T (s, a, s )), but on the one hand, this is noninformative to the agent (it knows T and hence can compute s from (s, a)), and even so, this fails to capture natural situations: for instance, if a lottery is such that the user has 1 % chance to win 101 and 99 % chances to win 0, with a cost of 1 in all cases, then the optimal policy is to play, but this is not supported by the most plausible outcome.

Given that we take expected utility as the criterion for decision making, a more natural choice is the successor s of s, a which maximises T (s, a, s )V π * M (s ), that is, which is both likely enough and rewarding enough for supporting the decision. Considering the lottery example again, the agent would learn 1 % × (V π * M (win) -1) > 99 % × (V π * M (lose) -1), which is indeed informative (this is closely related to von Neumann's elicitation of the value of winning vs losing).

However, this notion has the drawback of being sensitive to affine transformations of the reward function, while the decision process itself is not. For instance, if the reward function in the lottery example is modified by adding 101 to R(s) for all s, which does not change the optimal policies, then the previous inequality would become 1 % × (V M π * (win) -1) = 2.01 < 99 % × (V M π * (lose) -1) = 99, hence the advice would be with successor lose instead of win while the decision problem is the same. Hence at least, giving such advice requires the user and the agent to refer to a common, absolute numerical scale.

To fix this, we add an extra term to the inequality, which acts as a normalisation term while not requiring more insight of the user into the ramifications of her decision.

Definition 4 (gain-risk successor advice) Let M = S, A, T, R, γ be an MDP, π * be an optimal policy for it, and write V = min s∈S V π * M (s). An (optimal) gain-risk successor advice is a triple (s, a, s ) ∈ S × A × S such that (s, a) is an (optimal) action advice and satisfying

s ∈ arg max s T (s, a, s )V M π * (s ) + (1 -T (s, a, s ))V
This criterion is similar to maximal weighted utility, and requires exactly the same effort for the user to give advice.

It is in the interpretation of the advice by the agent that normalisation occurs. Intuitively, a gain-risk successor advice formalises the user saying "in that state, I would choose such action, expecting to reach such state, while aware of the risk to reach such other unwanted state".

Example 5 Consider a user who wants to go from City A to City B. There are two roads, X and Y, and one can easily switch road. Assume a GPS chooses X because it is shorter. Assume the user wants to take Y because she likes contemplating the canyon from there, but it may rain and the canyon would not be visible. An action advice would be "from A take Y", and would make the GPS take Y then switch to X asap. A gain-risk successor advice would be "from A take Y, with the aim of reaching a state where the canyon can be contemplated". The GPS would then consider taking Y until the canyon, then switch to X. Indeed, from the advice and the probability of rain, the GPS would infer information about the value of contemplating the canyon according to the user. Example 6 As another example, consider a lottery with 1/4 chance to win 100 and 1/2 chance to win 10. The hope (when playing) is to get 100, since this is probable enough and more rewarding. But if the first reward were 15, one would mainly hope to get 10 (which now contributes 10 × 1/2 = 5 to the expected value, vs 3.75), while still having "play the lottery" as the optimal action, so that action advice would be poorly informative. Indeed, it can be seen that the successor s indirectly provides information about the rewards, which is then useful for computing actions in other states.

Computing MMR Policies with Advice

In the setting of IRMDPs, once the agent has received an advice A of any type, all the information which it has is that the target reward function R is in the imprecise set R and is such that the MDP S, A, T, R, γ satisfies the advice. Write R ⊕ A for the set of all such reward functions, and M ⊕ A for the IRMDP S, A, T, R ⊕ A, γ . From M ⊕ A, the agent can compute a new MMR policy. In an iterative setting, as we consider in our experiments, the agent can display this new policy to the user, who can give new action advice, etc.

Definition 7 (min max regret with advice) Let M = S, A, T, R, γ be an IRMDP, and let A be an advice for M . A policy π : S → ∆(A) is said to be MMR-optimal knowing A if it satisfies π ∈ arg min

π ∈∆(A) S MR M ⊕A α (π ).
There is no reason in general for R ⊕ A to be a polytope. Still, we now give efficient ways to compute MMR-optimal policies with respect to R ⊕ A.

It is easy to modify Regan and Boutilier's approach (2009) to take optimal action advice into account. Precisely, referring to Figure 1, and keeping in mind that I a (s) is a variable which is true if and only if the adversary policy π g computed by the subproblem satisfies π g (s) = a, it is easily seen that an optimal action advice (s, a) can be integrated to the subproblem through the additional linear constraint I a (s) = 1 (or , equivalently, Q a (s) ≥ Q a (s) (∀a ∈ A)). Similarly, a (nonoptimal) action advice can be integrated by adding the constraint Q a (s) ≥ Q π * (s) (s).

The modification is more involved for gain-risk successor advice (s, a, s ), for which we need to refer to V inside the subproblem. For this, we use an extra (real-valued) variable V , meant to hold this value, and |S| extra 0/1 variables, written M (s), encoding the state s at which V is minimum.

Definition 8 (subproblem for gain-risk successors) Let M = S, A, T, R, γ be an IRMDP, let A = (s, a, s ) be a (optimal) gain-risk successor advice for it, and write R for min R∈ R min s∈S R(s). The subproblem for M with advice A is defined to be the subproblem of Figure 1 augmented with the constraint for the (optimal) action advice (s, a), variables V and M (s) (s ∈ S), and the constraints:

(1) T (s, a, s ) • V (s ) + (1 -T (s, a, s ))V ≥ T (s, a, s ) • V (s ) + (1 -T (s, a, s ))V (∀s ) (2) V ≤ V (s ) (∀s ) (3) s ∈S M (s ) = 1 (4) M (s ) ∈ {0, 1} (∀s ) (5) V ≥ M (s )V (s ) + (1 -M (s )) 1 1-γ R (∀s )
Constraints ( 2) and ( 5) realise a standard trick for forcing V = min s V (s ) in any optimal solution, so that it is easily seen that this program is correct.

Proposition 9 Let M = S, A, T, R, γ be an IRMDP, let A = (s, a, s ) be a gain-risk successor advice for it, and let π be a policy (as computed by the master problem). The optimal solutions of the subproblem for M and π with advice A are exactly at those reward functions R which satisfy A.

Experimental Results

We now report on experiments on synthetic MDPs, aimed at evaluating advice along the following dimensions:

• the kind of advice given to the user, optimal action advice vs optimal gain-risk successor advice, • the kind of interactions between the user and the agent, one-shot interaction vs iterative interaction (see below), • for iterative interaction, the impact of the number of interaction steps on the quality of the agent's policy, • for iterative interaction, the impact of the method used for selecting the advice (see below).

Scenarios of Interaction

We distinguish two types of scenarios. In the first one, which we call one-shot interaction, the agent equipped with an IRMDP first shows its MMRoptimal policy π * to the user, the user computes all pieces of advice (either optimal actions or optimal gain-risk successors) A 1 , A 2 , . . . , A k relative to this policy, and communicates them all to the agent. No further interaction occurs, and the agent computes an MMR-optimal policy knowing A 1 , A 2 , . . . , A k as in Definition 7. On plots, we refer to this policy by "OptAction-all" (resp. "GainRisk-all").

In the second scenario, which we call iterative interaction, the agent again shows its MMR-optimal policy to the user, but the user selects a single piece of advice A 1 and gives it to the agent. The agent then computes an MMR-optimal policy π * 1 knowing A 1 and shows it to the user, who selects a piece of advice A 2 relative to this new policy, gives it to the agent, and so on. We plot the quality of policies π * 1 , π * 2 , . . . , π * i , etc., as a function of i, where the ith iteration corresponds to an MMR-optimal policy knowing A 1 , A 2 , . . . , A i . On the one hand, we expect advice to be more informative in this iterative scenario, but on the other hand, a number of iterations is required before the agent gets as much advice in this scenario as it got with one-shot interaction, where all advice is given to it at the first step.

Finally, we studied different methods for the user to select a single piece of advice at each iteration. We report results for two methods proposed by [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF]: "Halve Largest Gap" (HLG) and "Current Solution" (CS).

Formally, given R, HLG selects the state s for which the "gap" [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF] then ask the user a "bound query" of the form "is R(s) ≥ b ?", where b is the midpoint of the gap. We adapt it to our setting by giving the optimal (action or successor) advice at s. Now, CS can be seen as a weighted version of HLG. Intuitively, this accounts for the fact that being uncertain about s is not so serious if s has little influence on the value and on the regret of our current best policy. Precisely, CS selects the state s for which the quantity

δ(s) = max R∈ R R(s) -min R∈ R R(s) is maximal.
max{ a∈A f (s, a)δ(s), a∈A g(s, a)δ(s)}
is maximal, where f (s, a) (resp. g(s, a)) is the occupation measure of s, a according to the MMR-optimal policy π * of M , as shown by the agent to the user (resp. according to the policy incurring the maximal regret to π * ).

We wish to emphasise than CS and HLG were not designed to cope with advice contexts as we investigate in this paper, in the sense that they were designed for reducing maximum regret [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF], without the advice referring to any target, concrete reward function whatsoever. Those methods however proved efficient in our context.

All in all, combining optimal action and optimal gain-risk successor advice, on the one hand, with HLG or CS, on the other hand, gives four different iterative interaction scenarios, each of which we analyse along the number of iterations. On plots, the scenarios are referred to by "OptAction-cs", "OptAction-hlg", "GainRisk-cs", and "GainRisk-hlg".

Finally, for all experiments we plot the quality of the MMR-optimal policy, computed without any advice. For the first experiments, we also plot the curves for the iterative scenario and bound queries ("mmr-cs" and "mmr-hlg").

We also want to mention that we ran experiments with a number of other definitions of advice (e.g., most probable successor, optimal one under various criteria) and with a number of other selection methods for a single piece of advice (e.g., restricting to advice on a most probable trajectory, to advice on a state as "close" as possible to a state with unknown reward, etc.). However, some combinations gave results quite uniformly worse than the methods listed above, and most of them gave similar results, which is why we stick to a few, previously investigated, methods.

Evaluation of Policies Our aim is to measure the quality of policies computed with advice of a certain type, selected with a certain method. For this, given that we consider advice meant to give information about the target reward function R (or about the optimal, target policy), our essential measure is the regret of the computed policies π * i with respect to R (Definition 1). To stick to natural scenarios (like GPS navigation devices), we computed the regret with a singleton distribution for α, at a so-called "starting state", hence measuring the regret of the policy for a specific task. We refer to this measure by "Regret in the user MDP".

As a reference, for the first experiments we also measure the maximum regret of the computed policy π * i with respect to the set of rewards R ⊕ A 1 ⊕ • • • ⊕ A k , to which we refer by "Regret in the agent MDP"; there, to be consistent with Regan and Boutilier's work, we use a uniform distribution over all states for α. We however want to mention that results are essentially the same with a uniform or singleton distributions, as confirmed by our preliminary experiments.

Regret in the agent MDP hence measures the extent to which the advice helps reducing the agent's uncertainty, while regret in the user MDP measures the extent to which it helped the agent to correctly identify the target reward function. This may be significantly different as soon as the target function is far from the "middle" of the set R.

Generic MDPs

We first ran experiments on generic MDPs, randomly generated using the same procedure as [START_REF] Regan | Regret-based reward elicitation for Markov decision processes[END_REF]. Precisely, we generated random MDPs with 20 to 50 states and with 2 to 4 different actions available at each state. The transition function was generated by drawing, for each pair (s, a), log(|S| × |A|) reachable states, and the probability of each was generated from a Gaussian. To model a generic goal-based task, we generated the target reward function by choosing a goal state g uniformly at random as well as a value R(g) drawn uniformly from [750,1000]. Now, to consider important levels of impreciseness, we built a set U ("unknowns") consisting of 2/3 of the states drawn at random; each of them got the same reward, drawn from [-600, +600], in the target R, and R was defined to be Π s∈U [-1000, +1000] (the agent only knows that for each s ∈ U , R(s) is between -1000 and +1000). The reward for all other states was fixed to 0 in both R and R.

We emphasise that with such settings, the agent is not even sure in general that g is the goal of the problem, since according to its uncertainty about R, it may be the case that some other state (in U ) has a higher reward.

We ran 50 simulations with different settings, each one for 10 iterations in iterative scenarios. The results, averaged over all simulations, are depicted on Figures 2, 3, and4.

Figure 2 (evaluation in agent MDP) clearly confirms that CS and HLG with bound queries are efficient methods for reducing the global uncertainty of the agent, a task they were designed for, while our advice, which is targetted at a specific reward function, performs badly (even worse than MMR without advice). The situation is reversed on Figure 3 (evaluation in user MDP), which shows that the target policy can be approached very quickly with advice dedicated to this task. However, in these dynamic scenarios, all methods using HLG or CS, and optimal action or gain-risk successor advice, essentially perform the same, despite the fact that they do not a priori have the same informative content.

The situation is different when we consider one-shot interaction. Figure 4 clearly shows that optimal action advice is useful (compared to the baseline MMR), but that optimal gain-risk successor advice is much more so.

Finally, Figure 4 also shows that iterative interaction is worthwhile: on average, less that 10 iterative communications of advice led to better results than one-shot interaction with optimal action advice, despite the fact that one-shot interaction provided no less that 8 to 24 pieces of advice at once, with an average of 17.

Grid MDPs

We next generated random MDPs simulating a grid world in which an agent must go from one square to another one. Such "grid MDPs" are per design much more regular than generic MDPs, and allow us to observe the utility of advice in environments were a policy can easily "come back" and "correct a mistake" (said otherwise, in which there are few or no dead-ends).

We considered grids of size 5 × 5 to 7 × 7 with one action per direction, including diagonals (plus "stay"). We also added a low probability for each action to fail (lead to a state adjacent to the intended destination). We drew one state g as the goal, and a set U of 10 to 15 other states as states with unknown reward. The reward R(g) for the goal was drawn from [80, 100], and that for states in U from [35,50]. All other states got a reward of 50. The IRMDP was defined by R = Π s∈U [0,200]. By this setting, we wanted to investigate whether the notions of advice would behave the same in environments where all states are rewarding.

Fig. 5 shows the results, averaged over 10 runs. Here, the iterative approaches perform still much better than for generic MDPs, as compared to one-shot interaction. This can be explained by little advice being available in one-shot interaction (between 2 and 16, with an average of 8). Indeed, since such MDPs are quite regular, min-max regret policies tend to perform rather well (to be close to most "good" policies), hence being subject to not so much advice. On the other hand, we can see that there is essentially no difference between GainRisk-all and OptAction-all. This can be explained by the fact that optimal actions have a clearly defined "preferred" successor, namely, the next step towards the goal, which is the most probable successor at the same time (otherwise, one of the other 8 actions would be better).

Hence successor advice adds no significant information.

Diamond MDPs

We finally designed a family of problems for which the reward of a few states suffices to generate a lot of uncertainty about the optimal policy. The construction is illustrated on Figure 6. Action a 0 has probability 0.5 to reach each child, a 1 , probability 0.3 to reach the left child and reaches a parent otherwise, and a 2 is dual. We generated R by letting R(s) = 0|∀s ∈ S \ ({g} U ) and drawing R(g), R(s)(∀s ∈ U ) from [600, 1000], [-600, 600], resp., where U denotes the middle horizontal line. The agent only knows that states in U have a reward in [-1000, 1000].

Hence each of the 2 n shortest trajectories from s 0 to g goes through one unknown-reward state, which makes this family a test case different from the previous ones.

Figure 7 shows the result. Iterative approaches perform badly, which we explain by the fact that CS and HLG have difficulties finding advice outside of the current trajectory. On the other hand, optimal gain-risk successors advice perform very well in one-shot interaction, like on generic MDPs. Here, clearly, the direction aimed at by the user, rather than the action alone, really helps the agent to learn.

Conclusion and future work

We have considered a generic notion of advice for Markov Decision Problems, allowing a user to give information to an agent about the reward function of the task at hand, and of minimax regret policies knowing advice. We have proposed a new type of advice and shown how to take it into account when computing minimax regret policies. We have shown its usefulness in some scenarios, through experiments. More generally, our experiments shed light on the pros and cons of various interaction scenarios and types of advice.

A short-term perspective of this work is to generalise it to a formal model of interaction with a user who has an Imprecise Reward MDP just as the agent. This is natural but leads to difficulties, in particular because the value function of a policy is not well-defined for Imprecise Reward MDPs. Another perspective is to generalise our study to MDP with imprecision on the transition function.

Figure 2 :

 2 Figure 2: Average regret in agent IRMDP (Generic).

Figure 3 :

 3 Figure 3: Average regret in user MDP (Generic).

Figure 4 :

 4 Figure 4: Average regret in user MDP (Generic).

Figure 5 :

 5 Figure 5: Average regret in user model (Grid).

Figure 6 :

 6 Figure 6: Diamond MDP: actions a 0 (left), a 1 , a 2 (right).

Figure 7 :

 7 Figure 7: Average regret in user model (Diamond).

It is easy to see that R • f α π is equal to s α(s)V π (s).


Abdallah Saffidine

Franc ¸ois Schwarzentruber

Bruno Zanuttini

Knowledge-Based Policies for Qualitative Decentralized POMDPs

Qualitative Decentralized Partially Observable Markov Decision Problems (QDec-POMDPs) constitute a very general class of decision problems. They involve multiple agents, decentralized execution, sequential decision, partial observability, and uncertainty. Typically, joint policies, which prescribe to each agent an action to take depending on its full history of (local) actions and observations, are huge, which makes it difficult to store them onboard, at execution time, and also hampers the computation of joint plans. We propose and investigate a new representation for joint policies in QDec-POMDPs, which we call Multi-Agent Knowledge-Based Programs (MAKBPs), and which uses epistemic logic for compactly representing conditions on histories. Contrary to standard representations, executing an MAKBP requires reasoning at execution time, but we show that MAKBPs can be exponentially more succinct than any reactive representation.

Introduction

Knowledge-Based Programs (KBPs) [START_REF] Fagin | Reasoning about knowledge[END_REF] describe policies that agents should perform according to their knowledge, such as 'if K i Φ then κ' where K i is the knowledge modality for agent i, Φ is a formula, and κ is a program. As shown by [START_REF] Lang | Knowledge-based programs as plans: The complexity of plan verification[END_REF]2013) for the single-agent case, KBPs offer compact representations of policies for planning problems. Moreover, arguably, they provide a natural level of expressivity for experts to design policies for autonomous agents.

We are interested here in multi-agent decision problems, for which we generalize KBPs. Precisely, we consider Qualitative Decentralized Partially Observable Markov Decision Problems (QDec-POMDPs), as formalized by [START_REF] Brafman | Qualitative planning under partial observability in multi-agent domains[END_REF]. Such problems involve multiple agents, decentralized execution, sequential decision, partial observability, and uncertainty.

A single agent executing a policy for such a problem must reason about what the other agents are executing, what they have observed, and what they believe or know. However, this is taken into account only indirectly by standard representations of policies. A drawback of this is that such policies are typically huge. By expliciting the reasoning about other agents' knowledge in Multi-Agent KBPs (MAKBPs), we provide more succinct representations. The counterpart is that executing MAKBPs requires reasoning, hence they do not constitute reactive policies. However, in many scenarios some reasoning at execution time may be affordable. Typical examples are applications in which executing atomic actions is not instantaneous (like in extraterraneous missions), so that deliberation can be performed in parallel.

Knowledge-based policies have been considered in other planning settings than that of QDec-POMDPs, in particular, they arise naturally in epistemic planning [START_REF] Bolander | Epistemic planning for single and multi-agent systems[END_REF]. Other works have taken inspiration from reasoning about knowledge to design approaches for multiagent (classical) planning [START_REF] Kominis | Beliefs in multiagent planning: From one agent to many[END_REF].

However, the originality of the (qualitative) Dec-PODMP model is that it assumes decentralized execution, but centralized planning. This makes it a challenging problem, as it requires to be able to plan offline a joint plan which can be executed in a decentralized fashion. The challenge is visible in the large body of work about the resolution of quantitative (stochastic) Dec-POMDPs (see [START_REF] Oliehoek | A concise introduction to decentralized POMDPs[END_REF], [START_REF] Dibangoye | Optimally solving Dec-POMDPs as continuous-state MDPs[END_REF] for instance).

Centralized planning with decentralized execution means that agents agree on a policy offline, then execute it independently of each other. Hanabi is a flagship example of such settings. In this cooperative card game with partial observability and limited communication, players typically agree on conventions before the game takes places. Researchers have started building computer players for Hanabi, notably by encoding human-designed policies (van den Bergh 2015; [START_REF] Cox | How to make the perfect fireworks display: Two strategies for hanabi[END_REF]. Furthermore, describing and using policies that involve epistemic reasoning to determine the next action is seen as a gateway to high-performance automated players [START_REF] Osawa | Solving hanabi: Estimating hands by opponent's actions in cooperative game with incomplete information[END_REF]). Yet, no formal frameworks allowing such policies have been put forward.

Example 1 (running) As a running example, assume Alice wants to meet Bob. She may take a train or a flight from her place to his, but there is a risk of air crew strike. Alice and Bob may call each other beforehand (centralized planning phase) to agree on the following plan.

Alice tries to fly. If there is a strike, she takes the train and listens to the radio to know whether Bob can know this. If the strike is not announced on the radio (hence Bob cannot know), after arriving at the station she will reach the airport to meet Bob there. Otherwise they will meet at her place of arrival. It can be seen that this plan, once agreed upon, can be executed successfully in a decentralized fashion.

Besides defining MAKBPs as a new representation of joint policies for QDec-PODMPs, we make the following contributions. We prove that this representation is as succinct as standard ones, e.g., joint policies trees, and we give families of problems for which it is exponentially more succinct. Contrary to standard representations, determining the action to execute next is nontrivial in MAKBPs, as it involves explicit reasoning about other agents' knowledge. We then investigate the complexity of this execution problem and that of verifying whether a given MAKBP solves a given QDec-POMDP, and we show that both these essential problems are intractable: both are PSPACE-complete if the horizon is bounded, and verification is undecidable otherwise. 1

Decentralized POMDPs

We define the planning tasks which we address in two steps; first the model, encoding the dynamics of actions and observations (Definition 2), then the planning task itself, which specifies an initial (belief) state, a goal, and a planning horizon (Definition 3). Our definitions essentially follow those given by [START_REF] Brafman | Qualitative planning under partial observability in multi-agent domains[END_REF]. We generalize them slightly by (1) allowing nondeterminism in the transitions and observations, (2) allowing the observations to depend on the previous state as well as the action and resulting state, and (3) allowing arbitrary observations rather than only the truth value of propositions.

For simplicity, we assume that all agents have the same actions, and do not consider explicit preconditions. 2 Definition 2 (factored QDec-POMDP model) A factored model for a Qualitative Decentralized Partially Observable Markov Decision Problem (QDec-POMDP) is a tuple M = I , X, A, Ω, T , where I , X, A, Ω are finite set of agents, propositions, actions, and observations, resp., and T is a transition function, which maps each couple (s, a) ∈ 2 X × A I to a set of couples {(s , ω)} ⊆ 2 X × Ω I .

A Boolean assignment s to X is called a state; s[x] denotes the value it assigns to x. An element a of A I is called a joint action, and specifies one (individual) action a i per agent i . We use similar notation for observations. The transition function encodes the dynamics of actions and observations: (s , ω) ∈ T (s, a) means that when the state is s and the agents take joint action a, it is possible that both the environment transitions to state s and each agent i receives the observation ω i . Note that the next states and observations depend on the current state and the joint action taken.

At execution time (when agents act), at any timestep t the environment is in some state s t ∈ 2 X . Each agent i (simultaneously and independently) chooses and takes an (individual) action a t i ∈ A, defining the joint action a t . Then the environment nondeterministically chooses a couple (s t+1 , ω t ) 1 A simple demonstration of executions of KBPs can be found in the tool Hintikka's world (http://people.irisa.fr/ Francois.Schwarzentruber/hintikkasworld/).

2 The trick to model unexecutable joint actions consists of adding a sink state to which any unexecutable joint action leads. from T (s t , a t ); it transitions to state s t+1 ; each agent i receives the individual observation ω t i ; and the process repeats. Definition 3 (factored QDec-POMDP) A factored QDec-POMDP is a quadruple Π = M, B 0 , g, H , where M = I , X, A, Ω, T is a factored QDec-POMDP model, B 0 ⊆ 2 X is the initial belief state, g is a Boolean formula over X called goal, and H ∈ N ∪ {∞} is the horizon.3

Histories and policies Let M = I , X, A, Ω, T be a QDec-POMDP model. A t-history for M is a sequence

h t = s 0 a 0 ω 0 s 1 a 1 ω 1 . . . s t-1 a t-1 ω t-1 s t
satisfying ∀t < t, (s t +1 , ω t ) ∈ T (s t , a t ). Of h t , the only information available to an agent i ∈ I is its local history

h t i = a 0 i ω 0 i a 1 i ω 1 i . . . a t-1 i ω t-1 i
, that is, the sequence of (individual) actions it has taken and (individual) observations it has received. We write H t for the set of all t-histories for M (M will always be clear from the context), and H t i for the set of all local t-histories for i . We also use notation

H ≤t = t t =0 H t and H ≤t i = t t =0 H t i . A (deterministic) t-policy for i is a mapping π i : H ≤t i → A. Action π i (h t i )
is the one which i should take when its local history so far is h t i . A joint t-policy π is simply a vector of t-policies, one for each agent i . A history h t = s 0 a 0 ω 0 . . . s t-1 a t-1 ω t-1 s t is said to be consistent with π if at all timesteps, each agent acts according to its policy, namely, for all timesteps t < t -1 and all agents i ,

a t +1 i is π i (a 0 i ω 0 i . . . a t i ω t i ). A joint t-policy π is valid for Π = M, B 0 , g, H if
for all H-histories s 0 a 0 ω 0 . . . s H-1 a H-1 ω H-1 s H with s 0 ∈ B 0 and consistent with π, the final state s H satisfies the goal g. Note that we require the final state to satisfy g: this implicitly requires that the agents know when g is achieved and maintain it until timestep H (e.g., using void actions if available). Finally, two joint policies are said to be t-equivalent (wrt Π) if they induce exactly the same sets of consistent t-histories.

In this paper, we are interested in joint policies which are computed offline in a centralized manner (as opposed to execution, which is decentralized), as is standard in the literature on Dec-POMDPs [START_REF] Brafman | Qualitative planning under partial observability in multi-agent domains[END_REF][START_REF] Oliehoek | A concise introduction to decentralized POMDPs[END_REF][START_REF] Dibangoye | Optimally solving Dec-POMDPs as continuous-state MDPs[END_REF].

Representations Desiging compact representations for (joint) policies is crucial, due to the combinatorial nature of H ≤t i . The most direct representations are (1) by policy trees, which the agent follows by branching on the observations received and executing the actions stored at the nodes, and (2) by finite state controllers, i.e., labelled automata in which transitions are fired by observations and each state holds an action to take (see [START_REF] Kumar | Dual formulations for optimizing Dec-POMDP controllers[END_REF]).4

w : {x}

w : ∅ w : {x} 1 2
Figure 1: Example of a Kripke structure (each world w is annotated with its valuation V (w))

A well-known drawback of such representations is that they can be huge even for simple problems. Observe indeed that there are as many as |Ω| t local t-histories, each of which can yield a distinct path in the tree or automaton. On the other hand, an advantage of using these representations is that they are reactive, in the sense that they are easily executable. Taking inspiration from [START_REF] Bäckström | Algorithms and limits for compact plan representations[END_REF], we formalize this as follows.

Definition 4 (execution problem) The execution problem takes as input a QDec-POMDP model M , an initial belief state B 0 , a joint policy π, an agent i , and a local history h t i such that there is a history h t consistent with π and inducing

h t i . It asks what action π i (h t i ) is, that is, what action π prescribes to i at timestep t + 1.
Definition 5 (reactive policy representation) A class R of representations of policies is said to be reactive if the execution problem restricted to policies represented in R is solvable in polynomial time.

Clearly, policy trees and finite state controllers constitute reactive representations: executing one consists of iteratively changing state according to the observation just received and taking the action found there. The rest of the paper provides a proper generalization of them, which is not reactive but has the essential advantage of being more succinct.

Background on Epistemic Logic

Let X be a set of variables and I be a set of agents. A Kripke structure represents an epistemic situation, that is, a description of the state of the variables and of what the agents know about it, about what the other agents know about it, etc. [START_REF] Hintikka | Knowledge and belief: an introduction to the logic of the two notions[END_REF]. This is done through a graph of possible worlds and undistinguishability relations ∼ i (for each agent i ). Intuitively, a possible world w represents a possible state over X (either the actual one, or one which an agent imagines) together with the epistemic situation for all agents, assuming that w is the actual world. Two such worlds are related by ∼ i if whenever the actual world is one of them, agent i thinks it might as well be the other one. Note that we model knowledge rather than beliefs (which might be false); precisely, we rely on an S5 n semantics, and in particular, an agent may know a formula Φ only if Φ is true.

Definition 6 (Kripke structure) A Kripke structure over X is a tuple S = W, (∼ i ) i∈I , V , where W is nonempty set of worlds, ∼ i is an equivalence relation over W for all agents i ∈ I , and V : W → 2 X is a valuation function, which associates an assignment to X to each world in W .

are (feasible) loops in the automaton, the policy can be executed for an infinite number of steps.

Figure 1 shows a Kripke structure with three worlds w, w , w (reflexive links are omitted for simplicity). Variable x is true in w and w , and false in w . Note that different worlds may have the same valuation. The ∼ 1 -equivalence classes are {w, w } and {w }. Hence when the actual situation is w, agent 1 thinks it might be w instead, and hence, it thinks that 2 may think that the actual world is w . Contrastingly, when the actual state is w or w , agent 1 knows that the actual state is not w . It can also be seen that when the actual world is w, agent 1 does not know the value of x, while it knows that x is true when the actual world is w .

Kripke structures are essentially used for giving semantics to epistemic formulas (over X and I ), which are logical formulas Φ generated by the following grammar:

Φ ::= x | ¬Φ | Φ ∨ Φ | K i Φ | KW i Φ
where x ranges over X, i over I , K i Φ is read "agent i knows that Φ holds", and KW i Φ is read "agent i knows whether Φ holds or not". An epistemic formula Φ is said to be subjective for agent i if all propositional variables x are in the scope of a K i or KW i modality. This means that Φ refers to the knowledge of i only; in particular, i is able to evaluate such a formula, while in general it does not know enough of the actual world to evaluate an objective (propositional) formula about it. Finally, the epistemic depth d(Φ) of Φ is the deepest nesting of modalities in Φ.

The truth condition S, w |= Φ is read "S, w satisfies Φ", and means that Φ is true at world w in the Kripke structure S. It is defined by induction on Φ, with the obvious definition for Boolean connectives:

• S, w |= x if x is assigned to true by V (w); • S, w |= K i Φ if ∀w , (w ∼ i w =⇒ S, w |= Φ) holds; • S, w |= KW i Φ if S, w |= K i Φ or S, w |= K i ¬Φ holds.
We insist that despite the fact that the actual world w is given in the definition, in general the agents do not know what the actual world is. For instance, on Figure 1 we have S, w |= ¬K 1 x ∧ K 1 (x ∨ ¬KW 2 x). In this paper, we use epistemic formulas as branching conditions in policies, and Kripke structures for providing them with operational semantics. In these structures, possible worlds essentially correspond to histories for the QDec-POMDP model at hand, and two histories are undistinguishable of each other for an agent i if they induce the same local history for i .

Multi-Agent Knowledge-Based Programs

We are now ready to introduce our new representation of joint policies for QDec-POMDPs. We build on Knowledge-Based Programs (KBPs) [START_REF] Fagin | Reasoning about knowledge[END_REF]) and on their use as policies for single-agent conformant planning [START_REF] Lang | Knowledge-based programs as plans: The complexity of plan verification[END_REF]. In a nutshell, single-agent KBPs represent policies by "programs" built using sequential composition, and branching and iterating with conditions about what the agent knows. We first generalize them to allow branching on the last observation received, through the constructor jo ("just observed"). This allows us to properly generalize reactive representations such as policy trees.

Let M = I , X, A, Ω, T be a QDec-POMDP model.

Definition 7 ((MA)KBP) A Knowledge-Based Program (KBP) for agent i is an expression generated by:

κ ::= | a | κ;κ | if Θ then κ else κ fi | while Θ do κ od
where is the empty program, a ∈ A is an action, and Θ is either an epistemic formula over X and I which is subjective for i , or a Boolean combination of atoms of the form jo(ω) for observations ω ∈ Ω. A Multi-Agent Knowledge-Based Program (MAKBP) is a vector of KBPs, one per agent i ∈ I .

We sometimes enclose a KBP inside bold brackets ([ . . . ]) to promote readability.

The epistemic depth d(κ) of a KBP κ is defined to be the maximal epistemic depth of a condition Θ occurring in it, and that of an MAKBP κ is defined to be the maximal epistemic depth of all individual KBPs κ i . We write K d for the class of all MAKBPs of epistemic depth at most d. 5 Finally, the size |κ| of a KBP is defined to be the number of symbols used for writing it, including the symbols used for writing the branching conditions, and |κ| is defined to be i∈I |κ i |. Example 8 (continued) Let strike and radio be variables encoding that there is an air crew strike and that it is announced on the radio, resp., and let plane A encode that Alice is in the plane. The plan of Example 1 would be represented by the MAKBP κ = (κ A , κ B ), with

κ A =                try-plane; if K A (¬plane A ) then take-train; turn-radio-on; listen-radio; if K A (¬K B strike) then to-airport fi fi κ B =
turn-radio-on; listen-radio; if K B (strike) then to-station else to-airport fi Note that conceptually, jo(ω) can be seen as the atom K i (o i = ω), if the dynamics of the problem is extended so that each state stores the last observation received by i in an extra variable o i . We also insist that jo constructs (resp. epistemic branching conditions) in the KBP of i refer to the last observation received by i itself (resp. to the knowledge of i itself, possibly about other agents' knowledge). Otherwise the KBP would not make sense, as i would not be able to evaluate its branching conditions at execution time.

Operational Semantics

We now define an operational semantics for MAKBPs, namely, a model for the agents to execute them. Importantly, recall that we consider decentralized execution (each agent executes its KBP independently of the other agents), but centralized planning, so that at execution time the agents know the QDec-POMDP Π as well as the whole MAKBP κ.

The operational semantics which we give is intended to be the straightforward one: each agent executes its own KBP faithfully, and all reason perfectly about the possible evolutions of the environment and of knowledge. However, providing a language which involves reasoning, as MAKBPs, with an operational semantics is a matter of choice, and we could as well study semantics involving approximate reasoning (e.g., bounded-depth epistemic reasoning). We leave this as a very interesting perspective for future work.

At execution time, when an agent i evaluates a branching condition such as [if K i K i Φ], it needs to reason about the current knowledge of i . This requires in particular to reason on what observations i has collected so far/on what actions it has taken. However, due to partial observability, i may not know exactly what actions i has taken so far, even if it knows what KBP i is executing. To cope with this, our semantics includes reasoning about the program counters in the KBP of each agent. The intended meaning of Γ, a, κ is that, provided that all formulas in Γ are currently true, i is about to execute action a, then it will execute the KBP κ. Definition 9 (program counter) Let i be an agent. A program counter for i is a triple c = Γ, a, κ with Γ = Θ (1) , . . . , Θ (k) , where each Θ (j) is either an epistemic formula subjective for i , or a Boolean combination of jo(ω) atoms, called the guard of c, a ∈ A is called the first action of c, and κ is a KBP called its continuation.

We will reason on what program counters may be "executed" after what others. We first define the set FPC (κ) of first program counters of a (nonempty

) KBP κ as fol- lows. If κ is of the form [a] (resp. [a ; κ ]), then FPC (κ) is the singleton { ∅, a, } (resp. { ∅, a, κ }). If κ is of the form [if Θ then κ else κ fi], then FPC (κ) is defined to be { {Θ} ∪ Γ , a , κ | Γ , a , κ ∈ FPC (κ )} ∪ { {¬Θ} ∪ Γ , a , κ
| Γ , a , κ ∈ FPC (κ )}, and while constructs are handled similarly. Finally, we define the control-flow graph of κ; intuitively, an edge c → κ c in G(κ) means that in an execution of κ, the first action of c will be followed by that of c , provided the guard of c is true. Definition 10 (control-flow graph) Let κ be a KBP. The control-flow graph of κ is the directed graph G(κ) = (V, → κ ) where (1) V is the smallest set of program counters which contains FPC (κ), and contains FPC (κ ) whenever it contains a program counter with continuation κ , and (2) → κ contains an edge from c = Γ, a, κ to c if and only if c is in FPC (κ ). Example 11 (continued) Bob's KBP κ B in Example 8 has four program counters:

c 0 B = (∅, turn-radio-on, [listen-radio; if . . . fi]), c 1 B = (∅, listen-radio, if . . . fi), c 2 B = ({K B (strike)}, to-station, ), c 3 B = ({¬K B (strike)}, to-airport, ),
and G(κ B ) has these as vertices, with c 0

B → κ B c 1 B , c 1 B → κ B c 2 B , and c 1 B → κ B c 3 B .
For simplicity, we assume that there is a unique first program counter in κ, written c 0 (κ) or c 0 (that is, that FPC (κ) is a singleton); given an initial belief state B 0 , this can always be enforced by precomputing the value in B 0 of all tests performed at the beginning of κ.

With this in hand, we give an operational semantics to MAKBPs, by defining the Kripke structure in which the agents evaluate branching conditions. The following definition defines both the structure and, implicitly, how it is progressed at execution time. Intuitively, this structure reflects what agents know about the epistemic structure (of all agents) as well as about the state variables X and the program counters of all agents. Technically, it is made of all possible extended histories, where an extended t-history h t is a sequence s 0 c 0 ω 0 s 1 c 1 ω 1 . . . s t c t consisting of the successive states and joint observations together with the (joint) program counters executed; a unique extended history is associated to each history s 0 a 0 ω 0 s 1 a 1 ω 1 . . . s t a t in the straightforward manner. Moreover, two extended histories are undistinguishable by an agent if and only if they have generated the same observations for it. 6Definition 12 (structure at time t) Let M be a QDec-POMDP model, B 0 be an initial belief state, and κ be an MAKBP. The structure for M, B 0 , κ at time t, is the Kripke structure S t (κ) = W t , (∼ t i ) i∈I , V over X, defined by induction on t as follows:

1. W 0 = {s 0 c 0 | s 0 ∈ B 0 }, 2. ∀i ∈ I , ∼ 0 i = W 0 × W 0 , 3. W t+1 is the set of all worlds h t s t c t ω t s t+1 c t+1 with (a) h t s t c t ∈ W t , (b) ∀i ∈ I , S t (κ), h t s t c t |= Γ t i , with Γ t i the guard of c t i , (c) (s t+1 , ω t ) ∈ T (s t , a t )
c t+1 )(x) = s t+1 [x].
Items 1 and 2 in Definition 12 state that it is common knowledge for the agents that the initial state is one in B 0 and that they are all about to start executing their KBPs, and that nothing more is known. In the definition of W t+1 , Item 3a states that possible worlds (extended histories) at time t + 1 are extensions of possible worlds at time t; Item 3b, that the program counter c t i was executable; Item 3c, that the new state and observations are consistent with the dynamics of M ; and Item 3d, that it is possible that c t+1 i is now the current program counter of i . Finally, Items 4 and 5 state that i distinguishes between histories only based on its local observations,7 and that the valuation of a world is determined by the current state of the environment.

Note that the situation at time t does not depend on the actual history, nor on the agent. It rather represents all possible evolutions of the environment and knowledge of the agents, i.e., what may have happened rather than what did happen.

Example 13 (continued) Write c 0 A , c 1 A for Alice's program counters (∅, try-plane, if . . . fi) and (K A (¬plane A ), taketrain, . . . ), resp. The initial belief state consists of two possible worlds (we write only the relevant variables):

h 0 = ¬strike 0 (c 0 A , c 0 B ) 0 , h 0 = strike 0 (c 0 A , c 0 B ) 0
At timestep 1, some possible worlds are:

h 1 = h 0 ¬strike 1 plane A 1 ¬radio 1 (c 1 A , c 1 B ) 1 h 1 = h 0 strike 1 ¬plane A 1 radio 1 (c 1 A , c 1 B ) 1 h 1 = h 0 strike 1 ¬plane A 1 ¬radio 1 (c 1 A , c 1 B ) 1
where h 1 , h 1 differ on whether the radio announced the strike at this step. Since the only observation is by Alice (whether plane A is true), we have

h 1 ∼ 1 B h 1 ∼ 1 B h 1 (Bob considers all three equally plausible), but h 1 ∼ 1 A h 1 and h 1 ∼ 1 A h
1 (Alice knows whether she is in the plane).

Still, we have h 1 ∼ 1 A h 1 , since Alice has not listened to the radio yet. Interestingly, at this point Bob does not know whether there is a strike, but he knows that Alice does (since he knows that she observed this as a result of trying to fly).

We finally define the operational semantics of KBPs, by defining when a history is consistent with an MAKBP.

Definition 14 (operational semantics) A t-history h t is said to be consistent with an MAKBP κ if for all timesteps t < t, each agent evaluates the epistemic branching condition Φ in its KBP by deciding S t (κ), h t |= Φ, where h t is the extended history associated to h t , and progresses its program counters and takes actions according to the straightfoward semantics for ;, if, while, and jo(ω).8

We emphasize that this semantics is well-defined. Precisely, since all epistemic conditions in the KBP of i are subjective for i (Definition 7), the test S t (κ), h t |= Φ is equivalent to i deciding whether the test is true at all situations which it considers actually possible, that is, to S t (κ), h t |= Φ for all histories h t consistent with the observations which it has received.9 Given that each agent also has all the information needed for building S t (κ) (namely M, B 0 , κ), because planning is centralized, the test indeed makes sense for each agent individually, at execution time.

Finally, we emphasize that we do not intend to design agents which compute or embark an explicit representation of S t (κ) at execution time. This notion serves only defining the operational semantics. Indeed, which action to perform at execution time can be computed from an intensional representation of S t (κ), with a procedure similar to model checking for succinct dynamic epistemic logic [START_REF] Charrier | A succinct language for dynamic epistemic logic[END_REF]) (see also our Proposition 18).

Notwithstanding the fact that there is not a single "correct" semantics, let us emphasize that our operational semantics builds on the multi-agent logic of knowledge S5 n and hence, that whenever agent i evaluates, say, K i K i Φ to , it is indeed the case that i knows Φ. Hence our semantics correctly captures faithful execution with perfect reasoning about the joint execution, by all agents.

Expressiveness and Succinctness

We now show that MAKBPs can represent any joint policy, at least as succinctly as standard representations like policy trees, and possibly exponentially more succinctly.

For this, we need to fix a concrete representation of QDec-POMDPs. Slightly generalizing the STRIPS-like representation proposed by [START_REF] Brafman | Qualitative planning under partial observability in multi-agent domains[END_REF], we assume that for each joint action a, a set of quadruples T a = {(ϕ (j) , e

+ , e

-, ω (j) ) | j ∈ J} is given, where each ϕ (j) is a propositional formula over X, each e

(j) + , e (j)
-is a set of propositions (with e (j)

+ ∩ e (j) -= ∅), and each ω (j) is a joint observation given as a tuple. Given a state s and a joint action a, this encodes T (s, a) = {(s ⊕ e

(j) + e (j) -, ω (j) ) | j is s.t. s |= ϕ (j) }, with s ⊕ e + e -= s s.t. ∀x ∈ e + , s [x] = , ∀x ∈ e -, s [x] = ⊥, ∀x ∈ X \ (e + ∪ e -), s [x] = s[x].
Finally, we assume that B 0 is given as a propositional formula over X, whose B 0 is the set of models.

Note that one can imagine other compact representations, especially representations based on influence diagrams or dynamic Bayesian networks [START_REF] Boutilier | Stochastic dynamic programming with factored representations[END_REF]. Our results would also hold with such representations, provided they allow to efficiently check that a given history is indeed generated by the dynamics, and to efficiently progress the values of the state variables.

To compare representations, we consider a quite general definition of a t-policy tree for a model I , X, A, Ω, T and an agent i ∈ I : an action a ∈ A is a 0-policy tree, and if a is an action, Ω 1 , Ω 2 , . . . , Ω k form a partition of Ω, and τ 1 , τ 2 , . . . , τ k are (t -1)-policy trees, then τ = (a, Ω 1 : τ 1 , Ω 2 : τ 2 , . . . , Ω k : τ k ) is a t-policy tree. The semantics is that when an agent executes such a tree, it first takes action a, then upon receiving an observation ω, it goes on by executing the tree τ j , where Ω j is the subset of Ω containing ω. The size |τ | (resp. |τ |) of a tree τ (resp. joint tree τ ) is defined to be its total number of nodes. Proposition 15 Let τ be a joint policy tree for a QDec-POMDP model M . Then there is an MAKBP κ which is equivalent to τ and has size linear in |τ |. PROOF. For all agents i ∈ I , define κ i to be κ(τ i ), where κ(τ ) is defined inductively as follows. If τ is reduced to a, then κ(τ ) is defined to be the KBP [a]. Otherwise τ must be of the form (a, Ω 1 : τ 1 , Ω 2 : τ 2 , . . . , Ω k : τ k ), and κ(τ ) is defined to be the KBP [a ; if ω∈Ω1 jo(ω) then κ(τ 1 ) else if ω∈Ω2 jo(ω) then κ(τ 2 ) . . . else if ω∈Ω k jo(ω) then κ(τ k ) else fi]. (Note that the else clause is never entered.) Clearly, κ(τ ) is equivalent to τ and of size linear in |τ |.

Since by their very definition, joint policy trees can represent any policy (modulo equivalence), we have complete expressiveness as an immediate corollary of Proposition 15.

Corollary 16 All (deterministic) joint policies for QDec-POMDPs can be represented as MAKBPs.

Importantly, the same result as Proposition 15 could be given for other reactive representations, such as finite state controllers (FSCs), were a goto construct added to the syntax of KBPs; this would indeed allow two parts of a KBP to share their continuation. Moreover, such a generalization would not change any result in this paper, and we only ignore this possibility to keep the presentation simple. Anyway, the result which we give next concerns any reactive class of representations, and hence does take FSCs into account.

Exponential Gains

We now exhibit a family of QDec-POMDPs for which (assuming NP ⊆ P/poly) there is no family of valid reactive policies of polynomial size, but for which there is a polysize family of valid MAKBPs, hence showing that the representation by MAKBPs can yield exponential gains in space. 10This result is directly inherited from the single-agent case (Lang and Zanuttini 2013, Prop. 2). However, this does not imply per se that reasoning about the other agents' knowledge is useful as far as succinctness is concerned (reasoning about its own knowledge might have been enough). We show that this is indeed useful, and even that increasing the epistemic depth allowed for MAKBPs always properly increases succinctness. Namely, for all d, we show that there is a family (Π n,d ) n∈N of QDec-POMDPs which has a family (κ n,d ) n∈N of valid MAKBPs of depth d, but no polysize valid MAKBPs of depth d with d < d, nor any in any reactive representation (assuming NP ⊆ P/poly).

Construction Broadly speaking, Π n,d encodes a problem in which some information passes through a series of d pairs of agents (i , i ) ( = 0, . . . , d -1), so that at each step, only one agent in the pair gets the information, as controlled by an (unobservable) variable x ; this agent must take one of two actions, depending on the information received.

The piece of information passed is precisely x -1 , that is, whether it is i -1 or i -1 who obtained the previous information. Finally, once passed, the value of x -1 is reset, so that i , i cannot reason on its value any more. In this manner, i , i must choose their action depending on whether they know that i -1 obtained the previous information, or they know that i -1 did; by induction, they must reason on whether they know that i -1 knows whether i -2 knows whether. . . , that is, on an epistemic formula of depth d.

Finally, for the last level, whether i d-1 or i d-1 obtains the information is controlled by whether a propositional formula ϕ is satisfiable, instead of a simple variable x d-1 ; assuming NP ⊆ P/poly, this prevents the last agent i d to have a polysize reactive policy, as this would give a nonuniform polytime algorithm for propositional satisfiability.

More precisely, the dynamics of Π n,d is designed so that the sequence of actions is forced in any valid policy. For this, we add a vector t of variables to the set X, meant to encode the current timestep, we add an encoding of s [ t] = s[ t] + 1 to the effect of each joint action, and we make each joint action a lead to a sink state if taken at a disallowed timestep.

All this can easily be encoded with a vector t of logarithmic size and a polynomial number of extra quadruples (ϕ, e + , e -, •) (where • represents a dummy observation).

The rest of the construction is as follows. A set of n state variables x ϕ,0 , . . . , x ϕ,n-1 represents propositions, and a 3CNF formula ϕ = 8n 3 -1 j=0 γ (j) on these variables is encoded in the state (over 8n 3 × 3 × (1 + log n ) Boolean variables). The n first steps in any valid policy for Π n,d force a specific agent i s to modify the values of x ϕ,0 , . . . , x ϕ,n-1 so that they encode a model ϕ, if possible, and to set variable x d-1 to if and only if ϕ is satisfiable; for more details, we refer the reader to (Lang and Zanuttini 2013, Prop. 12).

The problem also has a variable x for = 0, . . . , d -2, with unobservable value. At each timestep t = 8n 3 + n + 1 + , both i and i take an action which reveals the value of x -1 to i (resp. to i ) if s t [x ] is (resp. ⊥). Moreover, except for x 0 , whose value never changes, x -1 is reset to ⊥ at the same time. This transition can be encoded efficiently, through the four quadruples (ϕ, e + , e -, ω) of the form

(x -1 ∧ x , ∅, {x -1 }, (•, . . . , •, x -1 , •, . . . , •)), (¬x -1 ∧ x , ∅, {x -1 }, (•, . . . , •, ¬x -1 , •, . . . , •)), etc.

(where again,

• represents a dummy observation).

Finally, a last agent i d observes the CNF ϕ, and the bits encoding ϕ are reset to ⊥. At the last timestep H, the agents must together take a joint action so that • one of i 0 , i 0 takes action a (resp. a ) if s H [x 0 ] is (resp.

⊥), and the other takes a no-op,

• for = 1, . . . , d -1, one of i , i takes action a (resp. a ) if i -1 (resp. i -1 ) takes action a or a ,

• i d takes a (resp. a ) if i d-1 (resp. i d-1 ) takes a or a .

Any other joint action taken at this step sets leads to a sink state. The dynamics can be encoded efficiently as there are a polynomial (in n) number of joint actions allowed at all, and overall the size of Π n,d is polynomial in n.

We are now ready to state our main result. For Item 2, assume that there is such a family. Then take any 3CNF ϕ and simulate the MAKBP. If i d plays a then ϕ is satisfiable, otherwise it is unsatisfiable. This gives a polytime, polysize algorithm for deciding the satisfiability of a 3CNF formula over n variables, hence a nonuniform polytime algorithm for 3SAT, a contradiction.

Finally, for Item 3, we can show that for any valid MAKBP κ, the pointed structures S t (κ), h a and S t (κ), h a (t > 8n 3 + n + d + 1) are bisimilar up to depth d -2, i.e., that the subgraphs of S t (κ) centered at h a , h a and of radius d -1 are isomorphic [START_REF] Blackburn | Modal Logic[END_REF], whenever h a and h a have the same values for x , = 0, . . . , d -3, but a different one for x d-2 (by induction on d). Intuitively, this captures the fact that no epistemic condition Φ of depth less than K i d (KW i d-1 (. . . (KW i1 x 0 ))) can tear apart histories of the form h a (where i d must take action a) from histories of the form h a . As a consequence, any MAKBP allowing i d to take the correct action at the last timestep must have depth at least d.

Algorithmic Results

We now investigate the complexity of the main computational problems related to MAKBPs, viz. execution and verification, with input given in compact form as in the previous section. Note that the complexity of the general planning problem of deciding whether there exists an MAKBP which is valid for a given QDec-POMDP is the same as for any other representation, since MAKBPs are fully expressive (Corollary 16). Precisely, it is NEXP-complete (Brafman, Shani, and Zilberstein 2013, Corollary 1).

Recall that the execution problem asks what action i should take, given M, B 0 , κ, h t i . The membership proof in the next proposition follows the same structure as that, given by [START_REF] Charrier | A succinct language for dynamic epistemic logic[END_REF], that model checking for succinct dynamic epistemic logic is in PSPACE. This is not by coincidence, as progression for MAKBPs can be seen as DEL product updates (see Footnote 6).

Proposition 18 The execution problem for MAKBPs is

PSPACE-complete.
Proposition 19 The problem of deciding whether a given MAKBP is valid for a given QDec-POMDP at a finite horizon H ∈ N, given in unary, 11 is PSPACE-complete. SKETCH OF PROOF. For membership, by definition an MAKBP is not valid for Π if and only if there is a history consistent with it and which does not reach the goal. Since PSPACE is closed under nondeterminism and complementation, we have the result. For hardness, we reduce the execution problem (Prop. 18) to verification by using an action which sets a variable x g to , and defining the goal g to be x g . Then deciding whether the MAKBP is valid amounts to deciding whether this action is executed, hence the result. These propositions show in particular that MAKBPs can be executed and verified without explicitly computing nor maintaining the (exponential) knowledge structure S t (κ) at execution time. Hence the gain in succinctness with respect to reactive policies is not only at design time, when writing the policies, but also at execution time, when embarking and reasoning with them can be done in polynomial space.

Finally, since we allowed the while construct in KBPs, we also investigate verification at an indefinite horizon. The proof uses essentially the same ideas as the proof that epistemic planning with preconditions on knowledge is undecidable [START_REF] Bolander | Epistemic planning for single and multi-agent systems[END_REF]. Observe however that this result is not obvious, as the same problem is decidable in the single-agent case (Lang and Zanuttini 2012, Prop. 6).

Proposition 20 Determining if a given MAKBP terminates in finite time in all histories, for given QDec-POMDP model M and initial belief state B 0 , is undecidable.

Perspectives

Our first, obvious, perspective is to generalize Multi-Agent KBPs to the context of quantitative (stochastic) Dec-POMDPs [START_REF] Oliehoek | A concise introduction to decentralized POMDPs[END_REF]. To this aim, we will use epistemic logic with probabilities [START_REF] Fagin | Reasoning about knowledge and probability[END_REF] and its dynamic extension [START_REF] Kooi | Probabilistic dynamic epistemic logic[END_REF][START_REF] Van Eijck | Epistemic probability logic simplified[END_REF] instead of standard epistemic logic. Doing so will make a bridge between or work and the recently introduced notion of occupancy state [START_REF] Dibangoye | Optimally solving Dec-POMDPs as continuous-state MDPs[END_REF], which can be seen as the stochastic counterpart of our knowledge structures S t (κ). Another interesting perspective is to investigate approximate operational semantics for MAKBPs, for instance, semantics with reasoning at bounded modal depth, which may lead to a decidable verification problem. We also think that the expressivity of our framework allows to formalize real applications, such as Hanabi. Finally, the question of how to synthetize MAKBPs (that is, to plan) is very important; for this point, we intend to follow the direction of multi-agent epistemic regression.

  , where a t is the joint action made of the first actions of c t , (d) ∀i ∈ I , c t i → κi c t+1

	i	h	t s	t c	t ω	t s	t+1 c

i , 4. ∀i ∈ I , h t s t c t ω t s t+1 c t+1 ∼ t+1 t+1 iff h t s t c t ∼ t i h t s t c t and ω t i = ω i t ,

5. and ∀x ∈ X, V (h t s t c t ω t s t+1

  Proposition 17 For all d ≥ 2, the family (Π n,d ) n∈N is s.t. 1. there is a family (κ n,d ) n∈N of MAKBPs of depth d, so that κ n,d is valid for Π n,d and is polysize (in n), 2. assuming NP ⊆ P/poly, for any class R of reactive representations, there is no family (π n,d ) n∈N so that π n,d is valid for Π n,d and has a polysize representation in R, 3. for d < d, there is no family (κ n,d ) n∈N of MAKBPs of depth at most d , so that κ n,d is valid for Π n,d .

	SKETCH OF PROOF. For Item 1, the valid MAKBPs are
	the sequences of actions enforced by the problem. The only
	exceptions are for i s , for which we use the construction
	of (Lang and Zanuttini 2013, Prop. 12), and for the last ac-

tion, for which it is easily seen that it is enough for all agents i , i to execute

[if K(KW i -1 (. . . (KW i1 x 0 ))) then a else if K¬(KW i -1 (. . . (KW i1 x 0 ))) then a else no-op fi],

which indeed has depth d.

By assuming g to be a Boolean formula, we stick to the standard definition of a Dec-POMDP. However, it is easily seen that allowing epistemic goals, e.g., that all agents know the value of some variable, would not change the results in the paper.

 4 Note that finite state controllers constitute a much more general class of representations than policy trees. In particular, if there

The class K 0 consists of KBPs which do not branch, or branch only on combinations of jo(ω) atoms, since epistemic conditions are subjective and hence have depth at least 1.

For the readers familiar with dynamic epistemic logic, our construction amounts to the iterated product update of the initial situation encoding common knowledge of B 0 , by an event model built from the control-flow graphs of the KBPs.

We do not need to specify that an agent distinguishes two histories in which it took different actions, since KBPs are deterministic: this can occur only if it receives different observations.

We define condition jo(ω) to evaluate to ⊥ at the first timestep.

Equivalently, the test needs only be performed in the agent's internal, multipointed view of the situation[START_REF] Aucher | An internal version of epistemic logic[END_REF].

The complexity class P/poly (or "nonuniform P") is the class of problems for which for all n, there is an algorithm whose description is polysize in n and which correctly decides all instances of size n in polytime. The conjecture NP ⊆ P/poly is standard.

This amounts to considering that the input has at least size H.

Acknowledgments This work has been made possible by the existence of the working group MAFTEC of the French CNRS pré-GDR IA. The authors want to thank in particular Frédéric Maris, Tiago de Lima, Guillaume Aucher, and Alexandre Niveau for their contribution to the working group and to the early construction of this work.

Abdallah Saffidine is the recipient of an ARC DECRA Fellowship (DE150101351).