René Van Den Brink

Agnieszka Rusinowska
email: agnieszka.rusinowska@univ-paris1.fr

Frank Steffen
email: frank.steffen@uni-bayreuth.de

Measuring Power and Satisfaction in Societies with Opinion Leaders: An Axiomatization

Keywords: Collective choice, follower, opinion leader, power, satisfaction, axiomatization JEL Classification: D71, D85

) we proposed a two-action model for societies with opinion leaders. We introduced a power and a satisfaction score and studied some common properties. In this paper we strengthen two of these properties and present two further properties, which allows us to axiomatize both scores for the case that followers require unanimous action inclinations of their opinion leaders to follow them independently from their own action inclinations.

Introduction

The concept of opinion leadership plays a considerable role in sociology and marketing. Originally, it goes back to work by the Lazarsfeld group' (see, e.g., Katz and Lazarsfeld 1955, and Lazarsfeld et al. 1968). Following some critique on the original model Troldahl (1966) suggested his so-called two-cycle flow of communication model. Roughly speaking, it distinguishes between two phases in the communication process. Phase one is a flow of information from a sender (e.g., the mass media) to the members of the society, which is assumed to be a one-step process, i.e., the information goes directly to all members of the society. Phase two is a flow of influence on beliefs and behavior, which is assumed to be a two-step process. In a first step highly self-confident actors with strong opinions who are called opinion leaders form their own opinions based on additional information provided by experts, such as academics, while in a subsequent second step their opinion influences their so-called followers. These feel attracted by the opinion leaders holding them in high esteem and, under certain conditions, they are prepared to adopt their opinion for their own behavior. [START_REF] Asch | Effects of group pressure upon the modification and distortion of judgments[END_REF] This implies that opinion leaders possess some power over their followers as they may be able to influence their followers' behavior. [START_REF] Asch | Social psychology[END_REF] Since Troldahl's contribution the literature on opinion leadership has provided a strong body of knowledge of how and why opinion leaders influence followers choices (see Hoyer and Stockburger-Sauer 2007). Based upon Troldahl's model in van den Brink et al. (2011) we laid the foundations for a theoretical investigation of different opinion leader-follower structures and introduced a power and a satisfaction score, which allow us to compare and contrast different structures.

Our basic model considers societies being partitioned into opinion leaders, followers, and independent actors, who have to make a decision on an exogenous proposal. In line with Troldahl's (1966) model we assume that the proposal is distributed among all actors. Following Sinha and Raghavendra (2006) each actor faces a binary choice: by choosing the yes-action it can support the proposal in order to obtain a new state of the society, and by choosing the no-action it can reject it in order to remain with the status quo. Before making its choice each actor forms its own opinion on the proposal, i.e., without being influenced by any other actor. We call this the actor's action inclination. [START_REF] Asch | Studies of independence and conformity: a minority of one against a unanimous majority[END_REF] An action inclination contains the information which available state of the society an actor prefers to become reality, i.e., whether the outcome of the collective choice should be that the proposal is accepted or rejected. Hence, an actor can either have the action inclination to choose the yes-action in order to support the proposal or the no-action in order to reject it. This implies that there exists a relationship between an action inclination as defined above and the outcome of the collective choice. In addition to their action inclinations, the actors possess also constitutional inclinations, which, in the present context, are related to the organization of the society, or to make use of the words of Vanberg and Buchanan (1988) they are an actor's "preferences over potential alternative 'rules of the game' for the social community or group within which he operates. ... They reflect preferences that would emerge if he were to participate in choosing the constitution, in the broadest sense." In our context they determine (i) whether an actor is an opinion leader, follower, or independent actor, (ii) which opinion leader(s) an actor chooses if it is a follower, and (iii) the procedure for followers to follow their opinion leaders. For the purpose of our analysis we assume that constitutional inclinations are exogenous. This implies that (i) we have a given partition of our society into opinion leaders, followers, and independent actors, and that (ii) our opinion leader-follower relationships are already fixed, i.e., it is given which actors might influence the choice of action of certain other actors by exercising some power over them. Moreover, (iii) we assume that a unanimity requirement applies for followers to follow their opinion leaders. Action inclinations are left 'unspecified'. In line with Vanberg and Buchanan (1988) and Heckathorn (1987), who have introduced the distinction between both types of inclinations, we assume a lexicographical ordering of both types: constitutional inclinations are regarded to be on a 'higher level' than action inclinations as action inclinations have to be formed within the framework given by the constitutional inclinations. As we assume constitutional inclinations to be exogenous from now onwards, when we refer to action inclinations, we will just use the term inclinations.

In line with the inherent idea of opinion leadership we suppose that via informal discussions of the proposal the inclinations of the opinion leaders are becoming public information prior to the real decision, which implies that each follower is aware of the inclination of its opinion leader(s). [START_REF] Braham | Social power and social causation: towards a formal synthesis[END_REF] Only after these discussions, all actors will secretly (or simultaneously) choose their actions. These correspond with an actor's inclination, if it is an opinion leader or independent actor. If it is a follower with just one opinion leader, it will -independently of its own inclination -adopt the inclination of its opinion leader. If a follower has more than one opinion leader then it will choose an action against its own inclination if, and only if, a certain fraction of its opinion leaders have the same inclination, and this differs from its own inclination. For the purpose of the present paper we consider the specific, but quite usual, of power which goes back to Hoede and Bakker (1982). What they -and we in van den Brink et al. (2011) -call an inclination is called an action inclination in the present paper. [START_REF] Braham | Social power and social causation: towards a formal synthesis[END_REF] While our model allows that the public discussions may change the inclinations of some actors, we suppose that when choosing their action, and after that, inclinations do not alter.

case that this fraction is equal to one, i.e., unanimity. [START_REF] Brink R Van Den | An axiomatization of the disjunctive permission value for games with a permission structure[END_REF] Finally, based on the individual choices of all actors, a decision-making mechanism determines the outcome of the collective choice, i.e., whether the proposal is adopted or not. We assume that the collective choice is made by simple majority of the actions chosen by the actors.

As tools for the analysis of different opinion leader-follower structures van den Brink et al. (2011) introduced two scores being based on the notions of power and satisfaction where the latter contains the former as one component (see van den Brink and Steffen 2012). In the voting power literature power is, usually, ascribed to an actor if, given the chosen actions of the others, by changing its own action, the actor changes the outcome. It is said that the actor has a swing. Hence, roughly speaking, power in this context is defined as the ability of an actor, i.e., what the actor is able to do (by changing its action) against some resistance of others (represented by those chosen actions of the others, which are not in line with the 'new' action of the actor in question) irrespective of the actual occurrence of this resistance (see van den Brink and Steffen 2008 referring to Braham 2008). While this definition of power is sufficient for many applications, it implies a number of simplifying assumptions (see Morriss 1987/2002:154-156). Among others it assumes (i) that actors choose an action in line with their inclination, and (ii) that each actor's choice of action is not influenced by another actor. The implication of (i) is that for measurement purposes it is sufficient to consider the actions individually chosen by the actors and the resulting outcome, and to ignore the fact that inclinations are usually part of any definition of power defined as an ability. Following Morriss (1987/2002:26), 'abilities are things that we can do when we want'. As our opinion leader-follower collective choice situations allow for situations under which both assumptions above are violated, we have to relax both. This implies that for our purposes we have to consider the actors' inclinations for the measurement of power. Hence, in our context we ascribe power to an actor if, given the inclinations of the others, an actor by changing its inclination can enforce a change in the outcome via a change of its action. The power score that is introduced in van den Brink et al. ( 2011) is based on such power ascriptions and informs us about the power distribution among the members of a society with respect to their ability to affect the state of the society concerning a specific outcome.

According to van den Brink and Steffen (2012) satisfaction should be ascribed to an actor if its inclination corresponds with the outcome. This ascription is based upon the generic definition of satisfaction being the fulfillment of a desire. [START_REF] Brink R Van Den | Axiomatizations of Banzhaf permission values for games with a permission structure[END_REF] As a powerful actor in the sense of the power definition above can itself determine the outcome it desires, power is one feasible source of satisfaction. However, also a powerless actor can gain satisfaction. This satisfaction can result out of different types of luck (see van den Brink and Steffen 2012). Hence, we can say that, in our context, satisfaction is an important notion as it is the most extensive notion to characterize the position of an actor in a society (or organization) while the notion of power is of equal importance as it informs us about the fraction of satisfaction that an actor can enforce itself by the choice of its own action. [START_REF] Brink R Van Den | Measuring domination in directed networks[END_REF] The satisfaction score introduced in van den Brink et al. (2011) and which is applied in this paper is based on the satisfaction ascription defined above and, hence, tells us to which degree members of the society can be expected to end up with an outcome that they desire. [START_REF] Brink R Van Den | Measuring power and satisfaction in societies with opinion leaders: dictator and new opinion leader properties[END_REF] The paper is structured as follows. In Sect. 2 we provide a formal representation of our model and our power and satisfaction scores. In Sect. 3, which contains the main contribution of the present paper, we show that, in the present context, our power and satisfaction scores satisfy even stronger opinion leader properties than those studied in van den Brink et al. (2011). Moreover, we introduce two different normalizations and provide full axiomatizations of both scores, which differ in the normalization only. Finally, in Sect. 4 we wind-up the paper with a concluding remark.

2 Measuring power and satisfaction in opinion leader-follower collective choice situations

The model

We represent the structure of our society and the 'opinion leader-follower' relations by a bipartite directed graph (or bipartite digraph) (N, D) with a finite set of nodes N = {1, . . . , n} representing the actors, and D ⊂ N × N a coincide for the canonical set-up in the voting power literature and, hence, are often used as synonyms. However, for the model in the present paper this is not the case. See van den Brink and Steffen (2012) for a more detailed and critical discussion of the relationship between both notions. [START_REF] Brink R Van Den | Measuring domination in directed networks[END_REF] Consider, for example, collective decision making in the EU. In several countries there is a growing opposition against 'giving away sovereignty to Brussels'. This opposition clearly focuses on power and ignores satisfaction. However, if a country aimed to increase its satisfaction with the decisions made by the EU decision-making bodies, it might be useful to accept a transfer of their current EU decision-making rights and, hence, their power, to the EU. For example, suppose that the inclinations of The Netherlands and Germany coincide. Then, if the Germans were acting as de facto dictators in the EU decision-making bodies, The Netherlands having no longer any decision-making rights (and, hence, no power) would always be satisfied even they could never be successful. Instead, if the decision-making rights and power were more spread over the countries, one could expect that The Netherlands had some power and would have been successful in some instances, but would have been less satisfied. Hence, for the 'optimal' design of EU collective decision-making mechanisms one needs to know the importance of satisfaction and its components such as power and success for the member countries. [START_REF] Brink R Van Den | Measuring power and satisfaction in societies with opinion leaders: dictator and new opinion leader properties[END_REF] Note that this outcome needs not be in line with the action an actor has chosen. This would have been the case if we had applied the notion of success instead of satisfaction.

binary relation on N expressing that each actor is either an opinion leader, a follower, or an independent actor. Since we take the set of actors N fixed, we can represent a digraph (N, D) by its binary relation D. Let S D (k) = {j ∈ N : (k, j) ∈ D} be the set of successors of actor k ∈ N in digraph D, and let P D (k) = {j ∈ N : (j, k) ∈ D} be the set of k's predecessors in D. As we assume that each actor is either an opinion leader, follower or independent actor, we consider digraphs D such that: As explained in Sect. 1 we assume, that after the distribution of an exogenous proposal each actor will form its own inclination. The chosen inclinations are represented by the inclination vector I = (I 1 , ..., I n ) ∈ {0, 1} n . This is a vector which k th component, I k , is 1 if actor k has the inclination to choose the yes-action in order to support the proposal, and 0 if it has the inclination to choose the no-action in order to reject it. Now, we can define an opinion leader-follower collective choice situation as a pair (I, D) with I ∈ {0, 1} n and D ∈ D N .

|S D (k)| • |P D (k)| = 0 for each k ∈ N, ( 2
Next, let V = V (I, D) ∈ {0, 1} n denote the choice vector, that is a vector which k th component, V k , is 1 if actor k has chosen the yes-action, and 0 if k has chosen the no-action. Thus, the choice vector V = V (I, D) ∈ {0, 1} n is given by:

V k = I k if k ∈ OL(D) ∪ IND(D)
, and for k ∈ FOL(D) :

V k = x if I j = x for all j ∈ P D (k) I k otherwise, (2.2)
where x ∈ {0, 1}.

After all actors have chosen their actions, an outcome is resulting according to the decision-making mechanism in use. This is given by the collective decision function C: {0, 1} n × D N → {0, 1}, which assigns an outcome to every pair (I, D) ∈ {0, 1} n × D N , that is the value 0 if the collective decision is to reject, and the value 1 if the collective decision is to accept the proposal. We define the collective decision function by simple majority voting. Let for an action x ∈ {0, 1} and choice vector V = V (I, D) ∈ {0, 1} n the number of actors choosing the action x be denoted by n

x (V (I, D)) = |{k ∈ N : V k = x}|.
Restricting our analysis to situations in which the number of actors is odd, the collective decision function is defined, for each (I, D), as follows:

C(I, D) = 1 if n 1 (V (I, D)) > n 0 (V (I, D)) 0 if n 0 (V (I, D)) > n 1 (V (I, D)). (2.3)

Measuring power and satisfaction

In general, a score for bipartite digraphs representing opinion leader-follower collective choice situations is a function f : D N → IR n , which assigns an ndimensional real vector to every bipartite digraph on N . Here we consider the power and satisfaction scores introduced by van den Brink et al. (2011).

As explained in Sect. 1 we ascribe power to an actor if the actor, by changing its inclination, is able to alter the outcome, i.e., if the actor has a swing, and we measure the power of the actor in an opinion leader-follower collective choice situation by the actor's likelihood to be powerful. Formally, an actor k ∈ N has a swing in (I, D) according to collective decision function C if C(I, D) = C(I , D) with I k = I k and I j = I j for all j ∈ N \ {k}. In order to ascribe power to actor k we define a power score of actor k under a given inclination vector:

P OW k (I, D) = 1 if k has a swing in (I, D) 0 otherwise.
Then, the power score P OW : D N → IR n is given by:

P OW k (D) = I∈{0,1} n P OW k (I, D) for each k ∈ N. (2.4)
As explained in Sect. 1 we ascribe satisfaction to an actor if the actor's inclination corresponds with the outcome and we measure the satisfaction of the actor in an opinion leader-follower collective choice situation by the actor's likelihood to be satisfied. Formally, in order to ascribe satisfaction to an actor we define a satisfaction score of an actor under a given inclination vector, i.e., for each (I, D) ∈ {0, 1} n × D N and k ∈ N :

SAT k (I, D) = 1 if C(I, D) = I k 0 otherwise.
Then, the satisfaction score SAT : D N → IR n is given by:

SAT k (D) = I∈{0,1} n SAT k (I, D) for each k ∈ N.
(2.5)

Axiomatizations

In van den Brink et al. (2011) it is shown that both scores satisfy the following four properties. Let us denote a generic score by f :

D N → IR n . Symmetry If S D (k) = S D (j) and P D (k) = P D (j), then f k (D) = f j (D). Dictator property If D ∈ D N and h ∈ N is such that S D (h) = N \ {h}, then f h (D) = 2 n . Dictated independence If D, D ∈ D N and k ∈ N are such that |P D (k)| = |P D (k)| = 1, then f k (D) = f k (D ). Opposite gain property Let D, D ∈ D N , j ∈ IND(D), h ∈ OL(D) ∪ IND(D), and D = D ∪ {(h, j)}. Then f h (D ) -f h (D) = f j (D) -f j (D ).
Symmetry reflects a well-known principle stating that the value of a score for actors with a symmetric position in the bipartite digraph is the same. The dictator property states that, if there is a dictator (being a unique opinion leader who is followed by all other actors), then the score of the dictator is equal to the total number of possible inclination vectors. For the power and satisfaction scores this reflects that a dictator has the power to change the outcome by changing its own inclination and, if the dictator votes according to its inclination, then the outcome will be the inclination of the dictator. Dictated independence states that the score of a follower with one opinion leader does not change as long as this follower is dictated by a sole opinion leader, and reflects the idea that a follower who has only one opinion leader will always follow this opinion leader. The opposite gain property states that, if an actor becomes a sole opinion leader of another actor who was previously independent, then the sum of the scores of these two actors does not change.

In other words, if the opinion leader gains, then this goes fully at the cost of the follower. 9

Next, we strengthen two axioms that were introduced in van den Brink et al. (2011). First, horizontal neutrality states that, if a follower gets one more opinion leader, then the sum of scores of the 'new' and an 'old' opinion leader does not change. In other words, the change for the new opinion leader is opposite but in absolute value equal to the change for an 'old' opinion leader. [START_REF] Brink R Van Den | On the measurement of success and satisfaction[END_REF] Second, the equal gain property states that, if a follower gets one more opinion leader, then the changes in scores of this follower and of its new opinion leader are the same. and

D = D ∪ {(h, j)}. Then f h (D ) -f h (D) = f j (D ) -f j (D).
9 This principle is similar to several collusion neutrality properties introduced in the context of cooperative TU-games by e.g., Lehrer (1988), Haller (1994) and Malawski (2004), and applied to the so-called games with a hierarchical permission structure in van den Brink (2010). [START_REF] Brink R Van Den | On the measurement of success and satisfaction[END_REF] This is a stronger version of power neutrality for two opinion leaders. [START_REF] Deutschman | Diffusion of knowledge of the major new story[END_REF] This is a stronger version of the equal absolute change property. It is similar to Myerson's (1977) fairness for cooperative communication graph games, where it states that deleting a communication link between two players changes their individual payoffs by the same amount. In van den Brink (1997) this type of equal gain/loss property is stated in terms of the above mentioned games with a hierarchical permission structure.

Besides showing that the power and satisfaction scores satisfy these last two stronger axioms, the main contribution of this paper is to show that adding a further axiom which specifies what is the total sum of the scores over all actors (i.e., a normalization), characterizes the power and satisfaction scores. Obviously, since power and satisfaction are related but different concepts (see, e.g., Dowding 1996 and van den Brink and Steffen 2012) each will satisfy a different normalization. As normalization of power we take that the sum of all scores is equal to the total number of individual swings, i.e., for each inclination vector we count how many actors have a swing, and we add all these swings over all inclination vectors. As normalization of satisfaction we take that the sum of all scores is equal to the total number of individual satisfaction ascriptions, i.e., for each inclination vector we count how many actors have an inclination that corresponds with the outcome, and we add all these satisfaction ascriptions over all inclination vectors.

Power normalization For every

D ∈ D N it holds that k∈N f k (D) = I∈{0,1} n |{k ∈ N : k has a swing in (I, D)}|. Satisfaction normalization For every D ∈ D N it holds that k∈N f k (D) = I∈{0,1} n |{k ∈ N : I k = C(I, D)}|.
Next, we state the main result of this paper.

Theorem 1 (i) Let the choice vector V be defined by (2.2). A score f : D N → IR n is the power score POW : D N → IR n if, and only if, it satisfies symmetry, the dictator property, dictated independence, the opposite gain property, horizontal neutrality, the equal gain property, and power normalization. (ii) Let the choice vector V be defined by (2.2). A score f : D N → IR n is the satisfaction score SAT : D N → IR n if, and only if, it satisfies symmetry, the dictator property, dictated independence, the opposite gain property, horizontal neutrality, the equal gain property, and satisfaction normalization. To prove uniqueness, suppose that the score f : D N → IR n satisfies the seven axioms, and let D ∈ D N . We prove that f must be equal to POW in several steps. We first prove uniqueness in case there is at most one actor that is an opinion leader by induction on its number of followers.

First, suppose that the opinion leader is a dictator, i.e., there is an h ∈ N such that S D (h) = N \ {h}. Then the dictator property implies that f h (D) = 2 n . Since each actor k ∈ N \ {h} has no swing, power normalization implies that k∈N f k (D) = 2 n , and, thus, k∈N \{h} f k (D) = 2 n -2 n = 0. Symmetry then implies that f k (D) = 0 is determined for all k ∈ N \ {h}.

Proceeding by induction, suppose that f ( D) is uniquely determined whenever |S D (h)| > |S D (h)|. Take a j ∈ N \ ({h} ∪ S D (h)). Note that j is an independent actor since h is the only actor with successors. Consider D ∈ D N given by D = D ∪ {(h, j)}. Dictated independence and the induction hypothesis imply that f k (D) is uniquely determined for all k ∈ S D (h). Symmetry implies that there is a constant c ∈ IR such that:

f k (D) = c for all k ∈ N \ ({h} ∪ S D (h)).
(3.6)

The opposite gain property implies that:

f h (D ) -f h (D) = f j (D) -f j (D ), (3.7)
where f h (D ) and f j (D ) are given by the induction hypothesis. Then, with power normalization, ( From above it follows that f (D) is uniquely determined if D = ∅. [START_REF] Haller | Collusion properties of values[END_REF] Proceeding by induction, assume that f ( D) is uniquely determined whenever | D| < |D|.

We distinguish the following cases with respect to actor k ∈ N (of which at least one must occur):

1. If |P D (k)| = 1, then dictated independence and the case with a dictator considered before imply that f k (D) = 0 is uniquely determined. 2. If there is an j ∈ S D (k) with |P D (j)| = 1, then the opposite gain property implies that

f k (D) + f j (D) = f k (D \ {(k, j)}) + f j (D \ {(k, j)}). (3.8)
Since actor j is as in case 1, we determined f j (D). With the induction hypothesis f k (D \ {(k, j)}) and f j (D \ {(k, j)}) are determined. Thus, with

3.8), f k (D) = f k (D \ {(k, j)}) + f j (D \ {(k, j)}) -f j (D) is uniquely de- termined. (
3. If there is an j ∈ S D (k) with |P D (j)| ≥ 2, then take h ∈ P D (j) \ {k}. The equal gain property implies that

f k (D) -f k (D \ {(k, j)}) = f j (D) -f j (D \ {(k, j)}) (3.9)
and

f h (D) -f h (D \ {(h, j)}) = f j (D) -f j (D \ {(h, j)}). (3.10)
Horizontal neutrality implies that: Uniqueness follows similar as the uniqueness proof of part (i), but using the alternative satisfaction normalization.

f k (D) -f k (D \ {(k, j)}) = f h (D \ {(k, j)}) -f h (D). ( 3
Note that Theorem 1 characterizes the power score POW and the satisfaction score SAT by the same axioms except the normalization axiom. Thus, we have two comparable axiomatizations which exactly illustrate the difference between power and satisfaction, which lies in the normalization being applied. [START_REF] Heckathorn | Collective incentives and the creation of Prisoner's Dilemma norms[END_REF] This expresses the basic difference in measuring power and satisfaction.

Concluding remark

Having demonstrated that our power and satisfaction scores differ only in the normalization that is used, we would like to wind-up this paper with a remark on another difference between both scores. They also differ in how they treat situations where a dictator exists. Power normalization and the dictator property imply that the power score POW satisfies the property, that the power score of actors who are subordinates to a dictator is equal to zero. [START_REF] Hoede | A theory of decisional power[END_REF] Instead, satisfaction normalization and the dictator property imply, that the satisfaction score SAT satisfies the property that in case there is a dictator, the satisfaction score of a dictated actor is half of the satisfaction score of the dictator. This expresses another difference between measuring satisfaction and power. If a dictator exists, then the other actors cannot influence the outcome of the voting process since they have to follow the dictator, and therefore their power is equal to zero. However, also an actor that is subordinate to a dictator might end up with an outcome that corresponds with its inclination. Thus, ex ante a subordinate of a dictator will have its inclination coinciding with that of the dictator in half of the cases. Since a dictator always dictates the outcome, we arrive at a satisfaction score of the subordinate that is half of the satisfaction score of the dictator.

. 1 )

 1 where |X| denotes the cardinality of set X. Let OL(D) = {k ∈ N : S D (k) = ∅} be the set of opinion leaders, FOL(D) = {k ∈ N : P D (k) = ∅} be the set of followers, and IND(D) = N \ (OL(D) ∪ FOL(D)) be the set of independent actors in D. Since, by assumption (2.1) we have that OL(D)∩FOL(D) = ∅, the sets OL(D), FOL(D), and IND(D) form a partition of the set N . We denote the collection of all bipartite digraphs on N by D N .

11

 11

  Horizontal neutrality Let D, D ∈ D N , j ∈ FOL(D), g ∈ P D (j), h ∈ OL(D) ∪ IND(D), and D = D ∪ {(h, j)}. Then f h (D ) -f h (D) = f g (D)f g (D ). Equal gain property Let D, D ∈ D N , j ∈ FOL(D), h ∈ OL(D) ∪ IND(D),

  Proof (i) POW satisfying symmetry, the dictator property, dictated independence, and the opposite gain property is shown in van den Brink et al. (2011). It is obvious that POW satisfies power normalization. To show the equal gain property and horizontal neutrality 12 , let D, D ∈ D N , j ∈ FOL(D), h ∈ OL(D) ∪ IND(D), and D = D ∪ {(h, j)}. Note that POW k (I, D) = 1 implies that (i) POW k (I, D ) = 1 for k ∈ {h, j}, and (ii) POW k (I, D) = 0 implies that POW k (I, D ) = 0 for all k ∈ P D (j). Since [POW h (I, D) = 0 and POW h (I, D ) = 1] if, and only if, [I j = I h = I k for all k ∈ P D (j) and C(I , D) = C(I, D) for I j = I h = I h and I k = I k for all k ∈ N \ {h, j}] if, and only if, [POW j (I, D) = 0 and POW j (I, D ) = 1] if, and only if, [POW k (I, D) = 1 and POW k (I, D ) = 0 for all k ∈ P D (j)], POW satisfies the equal gain property and horizontal neutrality.

  ) and(3.7) yield (n -1 -|S D (h)|) + 1 + 1 = n -|S D (h)| + 1 linearly independent equations with the n -|S D (h)| + 1 unknowns, c and f i (D), k ∈ N \ S D (h). Thus, f (D) is uniquely determined.Next, we prove that f (D) is uniquely determined for all D ∈ D N by induction on |D|.

. 11 )

 11 With the induction hypothesis the values in graphs D \ {(k, j)} and D \ {(h, j)} are uniquely determined. Thus, with the three linearly independent equations (3.9),(3.10) and (3.11), the scores f k (D), f j (D) and f h (D) are uniquely determined. 4. If |P D (k)| ≥ 2, then f k (D) is uniquely determined as in the previous case (with the roles for k and j reversed). 5. Finally, symmetry implies that there is a constant c ∈ IR, such that f k (D) = c for all k ∈ IND(D). Since above we determined all f j (D) for j ∈ OL(D)∪ FOL(D), power normalization determines c. Thus, all f k (D), k ∈ N , are uniquely determined. (ii) SAT satisfying symmetry, the dictator property, dictated independence, and the opposite gain property is shown in van den Brink et al. (2011). It is obvious that SAT satisfies satisfaction normalization. To show the equal gain property and horizontal neutrality, let D, D ∈ D N , j ∈ FOL(D), h ∈ OL(D) ∪ IND(D), and D = D ∪ {(h, j)}. If C(I, D) = C(I, D ), then it must hold that actor j initially had to vote against its inclination and now can vote according to its inclination, because its new opinion leader h has the same inclination. Moreover, all 'other' opinion leaders of j must have the opposite inclination. Thus, for g ∈ P D (j) we have C(I, D) = I g = I j = I h and C(I, D ) = I j = I h = I g . So, SAT j (I, D ) -SAT j (I, D) = SAT h (I, D ) -SAT h (I, D) = SAT g (I, D) -SAT g (I, D ) = 1. Obviously, if C(I, D) = C(I, D ), then SAT j (I, D ) -SAT j (I, D) = SAT h (I, D ) -SAT h (I, D) = SAT g (I, D) -SAT g (I, D ) = 0. Thus, with (2.5) we have SAT j (D) -SAT j (D ) = SAT h (D) -SAT h (D ) = SAT g (D ) -SAT g (D), showing that SAT satisfies the equal gain property and horizontal neutrality.

In the current context this assumption appears to be in line with other findings in the literature. For instance,[START_REF] Asch | Effects of group pressure upon the modification and distortion of judgments[END_REF][START_REF] Asch | Social psychology[END_REF][START_REF] Asch | Studies of independence and conformity: a minority of one against a unanimous majority[END_REF]) results imply that when a group takes a unanimous position, people may feel more pressure to conform. A very recent study underpinning this view comes from an experiment conducted by[START_REF] Verhulst | Conformity in groups: the effects of groups on expressed attitudes[END_REF]. They found that participants were more likely to conform to the attitudes expressed by a unanimous group than by a non-unanimous group.

Note that satisfaction has to be distinguished from the 'preference free' notion of success, which is ascribed if an actor's choice of action corresponds with the outcome. Both notions

In van den Brink et al. (2011) it is already shown that horizontal neutrality holds, if the follower has exactly one opinion leader.

Note that this also follows from symmetry and power normalization.

A similar difference is shown by van den Brink and Gilles (2000) for the outdegree measure and the β-measure as scoring methods for directed graphs, highlighting that a normalization is not always so innocent as it might appear.

The power score POW even satisfies a stronger property, which states that if a follower has a unique opinion leader, then its power is equal to zero, i.e., if D ∈ D N , j ∈ FOL(D) and h ∈ OL(D) such that P D (j) = {h}, then f j (D) = 0.

Acknowledgements We would like to thank Marlies Ahlert, Shanti Chakravarty, Anke Gerber, Manfred Holler, David Hojman, Hartmut Kliemt, László Kóczy, Annick Laruelle, Garance Marechal, Jack Stecher, Jens Tiedemann, Viktor Vanberg, and two anonymous referees for comments and discussions.


Lucian Buşoniu

Rémi Munos

Optimistic planning for Markov decision processes

The reinforcement learning community has recently intensified its interest in online planning methods, due to their relative independence on the state space size. However, tight near-optimality guarantees are not yet available for the general case of stochastic Markov decision processes and closed-loop, state-dependent planning policies. We therefore consider an algorithm related to AO* that optimistically explores a tree representation of the space of closed-loop policies, and we analyze the near-optimality of the action it returns after n tree node expansions. While this optimistic planning requires a finite number of actions and possible next states for each transition, its asymptotic performance does not depend directly on these numbers, but only on the subset of nodes that significantly impact near-optimal policies. We characterize this set by introducing a novel measure of problem complexity, called the near-optimality exponent. Specializing the exponent and performance bound for some interesting classes of MDPs illustrates the algorithm works better when there are fewer near-optimal policies and less uniform transition probabilities.

Introduction

Stochastic optimal control problems arise in many fields, including artificial intelligence, automatic control, operations research, economics, etc. They can be modeled as Markov decision processes (MDPs) [START_REF] Puterman | Markov Decision Processes-Discrete Stochastic Dynamic Programming[END_REF], in which optimality is measured by a cumulative reward signal that must be maximized: the return. In this paper, we analyze an online, optimistic planning (OP) algorithm for discounted MDPs that have a finite number K of actions and N of possible random next states for every transition. This includes finite MDPs, as well as infinite (e.g. continuous-state) MDPs that satisfy the conditions.

At a given step of interaction with the system, OP develops a tree starting from a node containing the current system state and then iteratively expanding well-chosen nodes, where each expansion adds all N K children nodes containing all states reachable from the chosen node, see Figure 1. To choose which node to expand, first an optimistic subtree is constructed, by recursively navigating the tree along actions having the largest upper bound on their optimal return. Then, among the leaves of this subtree, a node is selected that maximizes the contribution of the node to the upper bound. After n such iterations, the algorithm returns an action which is applied to the system. A certain state may appear many times in the tree -as many as the number of ways it can be reached from the root; the simple variant of OP studied here does not merge information from these duplicates.

The main contribution of this paper is a nearoptimality guarantee for OP as a function of the number of expansions n, in terms of the simple regret: the loss in performance incurred by taking the action returned instead of the optimal action. We show that OP adapts to the complexity of the planning problem, by only expanding nodes with significant contributions to near-optimal policies. This notion is formalized so that the quantity of nodes with ε contribution to εoptimal policies is of order ε -β , with β a positive nearoptimality exponent. Then, we show that the simple regret is of order n -1/β for large n. When there are few near-optimal policies, as well as when the transition 1 Lucian Buşoniu is now with the Research Center for Automatic Control (CRAN), University of Lorraine, 2 avenue Forêt de Haye, Vandoeuvre-les-Nancy, France. This work was performed while he was with INRIA Lille.

Optimistic planning for Markov decision processes probabilities are nonuniform -both corresponding to having more structure in the MDP -β is small and the regret bound is better. To our knowledge, this is the first simple regret bound available for closedloop planning in stochastic MDPs (closed-loop policies are state-dependent, rather than open-loop action sequences; e.g., the dashed line in Figure 1 encloses part of the subtree of a closed-loop policy).

The exponent β is related to other measures of complexity used in the literature on bandits with many arms [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF]Bubeck et al., 2009b;[START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF]. However, a direct application of those results would look at the closed-loop policies as the elementary entity (arm), and would thus not take into account essential problem structure: the fact that a node belongs to many policies, and expanding it improves knowledge about all these policies. A more refined notion of complexity is needed to capture this global structure, and β serves this purpose.

It must be noted that we consider the simple regret (Bubeck et al., 2009a) which is different from the usual cumulative regret in bandit theory: we look at the suboptimality of the action returned after a given number of calls to the model, whereas the cumulative regret is the loss of reward incurred while exploring the environment (e.g., [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. Our measure corresponds to a numerical exploration-exploitation tradeoff, rather than an experimental one: we are interested in making the best possible use of a given numerical budget. Therefore, the simple regret is the appropriate measure of performance, and is directly related to the numerical complexity (i.e., number of calls to the model needed to return a near-optimal action). Note also that if each action returned by the algorithm is near-optimal, then the resulting policy is near-optimal.

While the bound does not directly depend on N and K, in practice they should not be too large, e.g. the probability mass should be concentrated on a few discrete next states. Fortunately this is true in many problems of interest. For example, combining continuous-state deterministic dynamics with random variables that only take a few discrete values leads to a small N . Such variables could be failure modes, job arrivals into a resource management system (e.g., elevator scheduling, traffic signal control), user input, etc.

Algorithmically, OP is rather simple, and can be seen as an extension of classical AO* heuristic search [START_REF] Nilsson | Principles of Artificial Intelligence[END_REF] to infinite-horizon discounted MDPs, similar to the AO* variant from [START_REF] Hansen | A heuristic search algorithm for Markov decision problems[END_REF]. AO* builds a complete plan, which can only be done in finite MDPs with goal states and may require arbitrarily long computation. OP finds general near-optimal solutions while the expansion budget is limited to n. It can actually be applied in an any-time fashion, without fixing n in advance, which gives it potential for online real-time control.

OP was proposed and empirically studied by [START_REF] Buşoniu | Optimistic planning for sparsely stochastic systems[END_REF]. It extends the earlier optimistic planning for deterministic MDPs (OPD) of [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], and in fact, in the deterministic case, OP and the regret bounds we derive here reduce to OPD and its bounds, respectively.

OP requires the full MDP model, including probability distributions over next states, whereas the class of sample-based planning methods only need to generate next states according to this distribution. [START_REF] Kearns | A sparse sampling algorithm for near-optimal planning in large Markov decision processes[END_REF] first proposed a "sparse-sampling" method that builds a uniform planning tree by sampling a fixed number of states for each action, up to some horizon, without adapting to the structure of the MDP. An adaptive-horizon extension was given by [START_REF] Péret | On-line search for solving Markov decision processes via heuristic sampling[END_REF]. An optimistic sample-based algorithm is "upper-confidence-trees" [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], which travels an optimistic path along the planning tree by choosing actions with maximal upper confidence bounds on the returns, and sampling states independently. UCT was extended to continuous actions by [START_REF] Mansley | Sample-based planning for continuous action Markov decision processes[END_REF]. UCT often works well in practice [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF] but good performance cannot be guaranteed in general since it may exhibit pathological behavior [START_REF] Coquelin | Bandit algorithms for tree search[END_REF]. [START_REF] Walsh | Integrating sample-based planning and model-based reinforcement learning[END_REF] avoid this problem with an optimistic extension of sparse sampling that comes with so-called probably-approximately-correct guarantees, of a different nature from the regret bounds we introduce here. [START_REF] Bubeck | loop optimistic planning[END_REF] do provide regret bounds for optimistic planning in stochastic problems, but only for open-loop sequences of actions, which are generally suboptimal.

Next, after providing in Section 2 the necessary notions concerning MDPs, we formalize the OP method in Section 3. In Section 4 we introduce the general regret bound and the insight behind it, and in Section 5 we specialize the analysis for some interesting types of MDPs. Section 6 concludes the paper. Proofs are collected in the supplementary material.

Background

Consider an MDP with state space X (taken countable for simplicity) and action space U . The probability that next state x ′ is reached after action u is taken in x is p(x, u, x ′ ), where p :

X × U × X → [0, 1]. After each transition a reward r ′ = r(x, u, x ′ ) is received, where r : X × U × X → R.
We assume that there is a finite number K of actions; that after applying any action in any state, the number of reachable next states is at most a finite N ; and that rewards are in [0, 1]. Denoting by k the discrete time index, the expected infinite-horizon discounted return (for short, value) of state x under policy π : X → U is:

V π (x) = E x k+1 ∼p(x k ,π(x k ),•) ∞ k=0 γ k r k+1 (1)
where x 0 = x, r k+1 = r(x k , π(x k ), x k+1 ), and γ ∈ (0, 1) is the discount factor. The goal is to control the system using an optimal policy π * , so that the value function V π : X → R is maximized for every x ∈ X. The resulting, maximal value function is denoted by V * and is unique. It is also useful to consider the optimal Q-function:

Q * (x, u) = E x ′ ∼p(x,u,•) {r(x, u, x ′ ) + γV * (x ′ )}.
The quality of action u k returned at state x k by the planning algorithm is measured by the simple regret:

R(x k ) = max u∈U Q * (x k , u) -Q * (x k , u k ) (2)
i.e., the loss incurred by choosing u k and only then acting optimally. A smaller regret is better, and optimal actions have 0 regret. If an algorithm achieves a simple regret of R for every state, the overall discounted return is R 1-γ -optimal [START_REF] Hren | Optimistic planning of deterministic systems[END_REF]. Note that throughout the remainder of the paper, we focus on the algorithm when applied from some particular state; we leave this dependence implicit most of the time.

Optimistic planning algorithm

To introduce OP, we first formalize the notions of tree and node illustrated in Figure 1. A state node is denoted s and is labeled by an actual state x. Many nodes s may have the same state x. Such duplicates could be merged which would close the tree into a graph; however here we restrict ourselves to the simpler variant of OP that ignores duplicates. By a slight abuse of notation, introduce also a function x(s) that returns the state label of a node. Define now the infinite planning tree T ∞ -of which Figure 1 only shows the first few nodes-recursively as follows. Initialize T ∞ with root s 0 labeled by x 0 , and recursively expand each node s ∈ T ∞ that does not yet have children. A node s is expanded by adding to it, for each u ∈ U , and then for each x ′ ∈ X with p(x(s), u, x ′ ) > 0, a child node s ′ labeled by x ′ . Thus the branching factor of each node is N K (smaller if there are fewer than N successors for some actions). Denote by C(s, u) the set of children s ′ corresponding to action u; and by C(s) = u∈U C(s, u). Note that T ∞ only includes the state nodes from Figure 1, and does not explicitly consider the actions. Nevertheless the actions are implicitly present in the connections between adjacent state nodes.

Algorithm 1 Optimistic planning

1: initialize tree: T 0 ← {s 0 } 2: for each iteration t = 0, . . . , n -1 do 3:

starting from s 0 , build optimistic subtree T † t :

4: while L(T † t ) ⊆ L(T t ) do 5: retrieve a node s ∈ L(T † t ) \ L(T t ) 6:
find optimistic action at s:

u † = arg max u s ′ ∈C(s,u) p(x(s), u, x(s ′ ))b(s ′ ) 7: add C(s, u † ) to T † t 8:
end while 9:

select leaf to expand:

s t ← arg max s∈L(T † t ) P(s) γ d(s)
1-γ 10: create C(s t ) and add them to T t , obtaining T t+1 11:

update b-values upwards in the new tree T t+1 :

b(s) =    R(s) + γ d(s) 1-γ , if s is leaf max u s ′ ∈C(s,u) p(x(s), u, x(s ′ ))b(s ′ ), else
12: end for 13: output u 0 maximizing lower-bound at s 0 Algorithm 1 gives OP as described in the introduction, which iteratively builds a finite tree contained at the top of T ∞ . The algorithm formalizes the notions of optimistic subtree and leaf contribution. The mapping L(•) provides the leaf nodes of its argument tree, and d(s) gives the depth of a node. The b-value b(s) is an upper bound on V * (x(s)). Moreover, if a leaf s at depth d is reached from the root via the path: s 0 , u 0 , s 1 , u 1 , . . . , s d = s, where the implicit actions are mentioned, then s has a probability P(s) and a partial return R(s) as follows:

P(s) = d-1 d ′ =0 p(x(s d ′ ), u d ′ , x(s d ′ +1 )) R(s) = d-1 d ′ =0 γ d ′ r(x(s d ′ ), u d ′ , x(s d ′ +1 ))
To choose the final action at the root, lower bounds are computed similarly to the b-values, but starting from 0 at the leaves.

The OP form given above is directly suitable for implementation. Next, we reinterpret OP as a search method in the space of tree policies, a form that is easier to analyze. A tree policy h is an assignment of actions to a subtree T h of T ∞ , h : T h → U , recursively taking into account only the nodes reached under the action choices made so far:

T h = {s ∈ T ∞ | s = s 0 or ∃s ′ ∈ T h , s ∈ C(s ′ , h(s ′ )) }
where actions h(s) are assigned as desired. The branching factor of T h is N . Denote the expected return (value) of one tree policy h by v(h), and the optimal, maximal value by v * .

A class of tree policies, H : T H → U , is obtained similarly but restricting the procedure to nodes in some finite tree T t considered by OP, so that all action assignments below T t are free. So H is a set of tree policies, where one such policy h ∈ H is obtained by initializing the free actions. Note that T H = T t ∩ T h for any h ∈ H.

Figure 1 shows a subtree corresponding to such a policy class, enclosed by the dashed line; a full tree policy would be obtained by continuing with the action assignments until infinity. Tree policies h are more general than the usual MDP policies π, which would be stationary, i.e., would always take the same action in a given state x. Tree policies h are allowed to take different actions for different nodes s, even if they are labeled by the same state x. While it is known an optimal stationary policy always exists, searching in a larger class does not prevent the algorithm from achieving (near-)optimality. We will typically deal only with tree policies and call them simply "policies", except where confusion with MDP policies is possible.

The value of any policy h belonging to some class H is lower-bounded by:

ν(H) = s∈L(TH ) P(s) R(s)
because the rewards that h can obtain below the leaves of L(T H ) are lower-bounded by 0. Note that the probabilities P(s) form a distribution over the leaves. Since rewards are also upper-bounded by 1, an upper bound on the value of h ∈ H is:

b(H) = s∈L(TH ) P(s) R(s) + γ d(s) 1 -γ = ν(H) + s∈L(TH ) c(s) = ν(H) + diam(H) (3)
where we introduced the notations c(s) = P(s) γ d (s) 1-γ , the contribution of leaf s to the difference between the upper and lower bounds, and diam(H) = s∈L(TH ) c(s), the diameter of H. This is indeed a diameter, diam(H) = sup h,h ′ ∈H ℓ(h, h ′ ), under the following metric on the space of policies:

ℓ(h, h ′ ) = s∈L(T h ∩T h ′ ) c(s)
The sum is taken over the shallowest nodes where h and h ′ are different. The diameter formula follows by noticing that for any s and u, s ′ ∈C(s,u) c(s ′ ) = γc(s) and so the contribution decreases monotonically with the depth, which implies that to maximize the distance between h and h ′ , we should make these policies different at the shallowest possible places in the tree. Since the policies must be the same at inner nodes of T H , the leaves of this tree are the shallowest nodes where we can make h and h ′ different. A useful interpretation of diam(H) is that it represents the uncertainty on the value of policies in the class.

With these notations, OP can be restated more concisely and intuitively, as follows. The algorithm selects at each iteration an optimistic policy class, which maximizes the upper bound among all classes compatible with the current tree T t :

H † t ∈ arg max H∈Tt b(H)
where the shorthand notation H ∈ T t indicates that class H is compatible with T t , i.e., that T H ⊆ T t . The optimistic class is explored deeper, by expanding one of its leaf nodes (making the action choices for that node definite). The chosen leaf is the one maximizing the contribution:

s t ∈ arg max s∈L(T H † t ) c(s)
Under the metric ℓ, this can also be seen as splitting the set of policies H along the longest edge, where H is a hyperbox with L(T H † t

) dimensions, having a length of c(s) along dimension s. Note a crucial property of the algorithm: expanding s t also refines many additional policy classes: all that reach s t with nonzero probability. The algorithm continues at the next iteration with the new, resulting tree T t+1 . After n iterations, a near-optimal policy class is chosen, by maximizing this time the lower bound:

H * n ∈ arg max H∈Tn ν(H) (4)
intuitively seen as making a safe choice. The action returned by the algorithm at the root is the first action chosen by H * n . Of course, the algorithm may also return the multi-step policy H * n , useful for taking decisions along several steps of interaction.

We recall that the equivalent OP form in Algorithm 1 is more suitable for implementation than this abstract form.

Analysis of optimistic planning

The complexity of the tree policy space for a given MDP will be characterized in terms of a constant called near-optimality exponent. The dependence of the regret on this exponent and the number of expansions n will be studied. Consider any node s on the complete, infinite planning tree T ∞ . Define n(s) to be the largest number, for any policy h whose subtree contains s, of leaves of the subtree T hs ∈ T h containing only nodes with larger contributions than s:

n(s) = sup T h ∋s |L(T hs )| , T hs = {s ′ ∈ T h | c(s ′ ) ≥ c(s) }
T hs is indeed a proper subtree since c(s) decreases monotonically along paths in T h . A policy subtree is schematically represented in Figure 2, together with an example of subtree T hs . Define using n(s) also the quantity α(s) = n(s)c(s). An essential property of α is that it relates s to the diameter of some policy classes that have it as a leaf. Specifically, the diameter of any class among whose leaves c(s) is largest, is upper-bounded by N γ α(s).

T h L( ) T hs s T hs
Figure 2: An infinite policy tree T h , and a subtree T hs for some s.

Finally, define for each ε the set of nodes:

S ε = s ∈ T ∞ (i) α(s) ≥ ε and (ii) ∃h ∋ s, v * -v(h) ≤ N γ α(s) (5)
Condition (i) requires the node to have a sizable contribution in terms of α, and (ii) that the node belongs to a near-optimal policy. The following main result holds.

Theorem 1. Let β ≥ 0 be any constant so that:

|S ε | = Õ(ε -β ), i.e. |S ε | ≤ a log 1 ε b ε -β (6)
where a, b > 0 are some constants. 2 The simple regret R n of the action chosen by OP after n node expansions satisfies for large n:

R n = Õ(n -1 β ) if β > 0 O(exp[-( n a ) 1 b ]) if β = 0
The constant β is the near-optimality exponent. It is important to note that OP does not require knowledge of the value of β, and yet, as the result shows, it automatically adapts to this value.

The measure β is connected to other complexity measures from optimistic optimization (bandits) and planning, such as the zooming dimension [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], the near-optimality dimension (Bubeck et al., 2009b), or the branching factor of near-optimal action sequences for OPD [START_REF] Hren | Optimistic planning of deterministic systems[END_REF] and open-loop optimistic planning (OLOP) [START_REF] Bubeck | loop optimistic planning[END_REF]. Characterizing the complexity of the planning problem by using these measures would essentially look at the individual tree policies as the elementary entity, and the analysis could only interpret the algorithm as a hierarchical search in the space of such policies. OP has this hierarchical component, which is realized by refining the optimistic policy class H † t . However, OP does more than just this: since the chosen node s t belongs to all the policy classes that reach it with a positive probability, expanding it refines all these classes, not just the optimistic one. This subtler, global effect must be captured in the definition of problem complexity, and this is achieved by introducing the quantity α(s) to describe the global impact of a node on the policies it belongs to, and by defining S ε and β in terms of individual nodes and not directly policies.

Therefore, the analysis intuitively says that OP finds a near-optimal policy by only expanding those nodes that have a large impact on near-optimal policies. As the number of such nodes decreases, the sets S ε are smaller, which is characterized by a smaller β, and the problem becomes easier; in particular, β = 0 means S ε grows logarithmically instead of polynomially. The definition (5) of S ε highlights two ways in which a problem can be easier: the transition probabilities are less uniform, leading to fewer nodes with large α; or the rewards are concentrated on a few actions, leading to fewer near-optimal policies. To formalize these intuitions, the next section will provide values of β for several representative types of MDPs, exhibiting varying degrees of structure in the rewards and probabilities.

Proof sketch of Theorem 1. We outline here how the result is obtained (see the supplementary material for the complete proof). The first big step is to show that the regret is related to the smallest α among expanded nodes, α * = min t=0,...,n-1 α(s t ). This is true because (a) the suboptimality of the near-optimal policy class H * t (and hence the regret of the root action it would choose) can be bounded at every iteration by the diameter of the optimistic policy: v * -ν(H * t ) ≤ diam(H † t ), and (b) using the essential property of α, this diameter is in turn at most N γ α(s t The near-optimal policy will not decrease in quality over iterations, which means the overall regret is bounded by N γ α * . The second major part of the proof is that the algorithm always usefully works to decrease the value of α * -formally, that all the nodes it expands are in S * α , so that n ≤ |S * α |. Connecting all this with the definition of β, which implies |S * α | = Õ(α * -β ), the overall regret bound is obtained.

Regarding the time complexity of OP, at the expense of some extra memory, each iteration can be brought down to O(d(s t )), the depth of the expanded node. Depths generally depend on β, but to obtain a range notice they are between O(log n) when the tree is developed uniformly and O(n) when a single path is developed (see also next section). So the overall complexity is between O(n log n) and O(n 2 ). Furthermore, while here we focus on the near-optimality perspective, our result can also be interpreted the other way around: to achieve ε regret, a budget n on the order of ε -β should be spent.

Some interesting values of β

To add meaning to the near-optimality exponent β, in this section we provide its value for several inter-esting special cases. We obtain smaller values when the MDP has "more structure", namely when there are non-uniform probabilities or rewards. The earlier OPD regret bounds [START_REF] Hren | Optimistic planning of deterministic systems[END_REF] are recovered in the deterministic case, showing that the OP guarantees encompass those of OPD as a special case.

Uniform rewards and probabilities

In this case, the rewards of all transitions are equal, and for any action, the probability of reaching one of the N next states is 1 N . Proposition 2. In the uniform case,

β unif = log N K log 1/γ and R n = O(n -log 1/γ log N K ).
One interpretation of β is that the argument of the logarithm at the numerator is an equivalent branching factor of the tree that OP must explore. A branching factor of N K means that OP will have to explore the whole planning tree in a uniform fashion, expanding nodes in the order of their depth. So the uniform MDP is an interesting worst case, where β is the largest possible. (Notice also that in this case the bounds do not have a logarithmic component, so O is used instead of Õ.)

In fact, the regret bound of OP in uniform MDPs is the same as that of a uniform planning algorithm, which always expands the nodes in the order of their depth. However, the uniform algorithm can guarantee only this regret bound for any problem, whereas in nonuniform problems, OP adapts to the value of β to obtain better guarantees.

Proving the regret of the uniform algorithm helps in understanding the upcoming discussion on worst-case regret, so it is done here. Consider the uniform algorithm has expanded all nodes at depth D -1, after n expansions. Then:

v * ≤ max H∈Tn b(H) = max H∈Tn [ν(H) + s∈L(TH ) P(s) γ d(s) 1-γ ] ≤ max H∈Tn [ν(H) + s∈L(TH ) P(s) γ D 1-γ ] = max H∈Tn ν(H) + γ D 1-γ = ν(H * n ) + γ D 1-γ
where H * n is the policy class returned by (4

). So R n ≤ v * -ν(H * n ) ≤ γ D 1-γ , and from n ≥ (N K) D -1 N K-1 after some calculation R n = O(n -log 1/γ log N K ).
This regret is also the smallest achievable in a worstcase sense, which means that for any planning algorithm and value of n, one can construct a problem for which the regret is R n = Ω(n -log 1/γ log N K ). To see this, choose the largest D so that n ≥ (N K) D -1 N K-1 , assign uniform probabilities everywhere, rewards of 1 for some arbitrary policy h * but only starting from level D + 1 onward, and rewards of 0 everywhere else. Then, both OP and uniform planning have uniformly expanded all nodes up to D -1 but none at D + 1, so they have no information and must make an arbitrary action choice, which may not be optimal, leading to a regret of γ D+1

1-γ = Ω(n -log 1/γ log N K ). An algorithm that does not expand uniformly may miss the optimal policy for an even larger number of expansions n, so their regret is at least as large. This fact also shows that OP behaves correctly in the uniform case: as long as only uniform rewards and probabilities are observed, the tree must be expanded uniformly, and this is reflected in the regret bound.

Finally, note that in the deterministic case, when N = 1, the regret bound of OPD for the uniform-reward case is recovered: R n = O(n -log 1/γ log K ).

Structured rewards

In this case, probabilities are uniform but a single policy has maximal rewards (equal to 1) for all transitions, and all other transitions have a reward of 0, see Fig- subtree of optimal policy, where each transition is associated with a reward of 1. Thin lines: the rest of the tree, associated with 0 rewards.

Proposition 3. In the case of structured rewards, if

N > 1, β rew = log N log 1/γ (1 + log K log N/γ ), whereas if N = 1, β rew = 0 and R n = O(exp(-n a )
) for some constant a.

The values of β rew are smaller than β unif , so the guarantee takes advantage of the additional structure introduced in the problem by the reward function.

In the deterministic case, β rew = 0, the problem becomes easy and the regret is exponential in n, having the form in the second branch of Theorem 1 for b = 1. This is the same bound that OPD obtains when a single policy is optimal [START_REF] Hren | Optimistic planning of deterministic systems[END_REF].

Examining the algorithm reveals that it will only ex-plore the optimal policy's subtree, with branching factor N , so the ideal value for β is log N log 1/γ . Improving the analysis to avoid this dependency is a topic for future work.

Structured probabilities

Finally, we consider problems where the rewards for all transitions are equal, but the transitions have significantly different probabilities. Take for simplicity identical Bernoulli transitions: N = 2 and the two successors of any state (and thus state node) have probabilities p and 1 -p, so that p is close to 1.

Proposition 4. In the Bernoulli case, for p close to 1,

β prob = log Kη ′ log 1/(pγη ′ ) , where η ′ = e η η and η = log 1/(pγ) log 1/(γ(1-p))
In the deterministic case, when p → 1, η → ∞ leading to η ′ → 1, and β prob → log K log 1/γ , recovering the uniformcase bound for N = 1 (i.e., the uniform-reward case). Nearby, when p is large, β ≈ log K log 1/γ , and OP expands "almost" only a tree with branching factor K. When the probabilities are uniform, η = 1 would lead to β prob = log eK log 2/eγ , and β unif , which was developed specifically for that case, is better.

Conclusions

We have analyzed the regret of a planning algorithm for stochastic MDPs, which optimistically explores the space of closed-loop planning policies. The core feature of this method is that it adapts to the complexity of the planning problem, encoded in the near-optimality exponent β. An immediate topic for further research is the form of this exponent for an MDP with arbitrary transition probabilities. Based on the special cases for β studied, we expect it to decrease as the distribution becomes less uniform.

The basic form of OP studied here can benefit from many algorithmic improvements, and analyzing their effect on the regret would be very interesting. For example, since OP is similar to AO*, improvements originally developed for classical AO* can almost directly be applied, such as closing the tree into a graph upon encountering duplicate states [START_REF] Hansen | A heuristic search algorithm for Markov decision problems[END_REF]. In online control, an essential improvement is reusing information across interaction steps. This could be done by maintaining an approximate value function (for the b-and/or ν-values), used to initialize leaf values and updated with tree data. In this context, near-optimality guarantees for approximate value iteration could be useful to improve the regret bounds under smoothness assumptions on the MDP [START_REF] Szepesvári | Efficient approximate planning in continuous space Markovian decision problems[END_REF][START_REF] Rust | Numerical dynamic programming in economics[END_REF].

OP does not assume any knowledge about the complexity of the problem, e.g. it does not require to know β. Deriving algorithms that, when such prior knowledge is available, exploit it to obtain better performance guarantees is an important open issue.

Supplementary material to "Optimistic planning for Markov decision processes": Proofs

Proof of main result

Recall that to prove Theorem 1, it must first be shown that the regret of the algorithm is related to the smallest α among expanded nodes (which will be done in Lemma 6), and then that the algorithm always works to decrease this smallest α (done in Lemma 7). A preliminary result is also needed.

Lemma 5. The ν-values of the near-optimal policy classes increase over iterations:

ν(H * t+1 ) ≥ ν(H * t )
, where H * t ∈ arg max H∈Tt ν(H).

Proof. Consider first one policy class H, split by expanding some leaf node s ∈ L(T H ). One child class H ′ is obtained for each action u, and we have u). By easy calculations, since the rewards are positive, the terms that nodes C(s, u) contribute to ν(H ′ ) add up to more than the term of s in ν(H), and the other terms remain constant. Thus ν(H ′ ) ≥ ν(H). Then, among the policy classes H t ∈ T t , some are split in T t+1 and some remain unchanged. For the children of split classes ν-values are larger than their parents'; while ν-values of unchanged classes remain constant. Thus, the maximal ν-value increases across iterations. Note it can similarly be shown that b(H † t+1 ) ≤ b(H † t ).

L(T H ′ ) = (L(T H ) \ {s}) ∪ C(s,
Lemma 6. Define α t = α(s t ), the α value of the node expanded at iteration t; and α * = min t=0,...,n-1 α t . The regret after n expansions satisfies R n ≤ N γ α * .

Proof. We will first bound, individually at each iteration t, the suboptimality of ν(H * t ), by showing:

v * -ν(H * t ) ≤ diam(H † t ) ≤ N γ α t (7)
To this end, observe that:

ν(H † t ) ≤ ν(H * t ) ≤ v * ≤ b(H † t ) (8)
The inequality ν(H * t ) ≤ v * is true by definition (ν(H * t ) is a lower bound on the value of some policy, itself smaller than v * ). For the leftmost inequality, H * t maximizes the lower bound across all policy classes compatible with the current tree, so its lower bound is at least as large as that of the optimistic policy class H † t . Similarly, for the rightmost inequality, since H † t maximizes the upper bound, its upper bound is immediately larger than the true optimal value. Using this string of inequalities, we get:

v * -ν(H * t ) ≤ b(H † t ) -ν(H † t ) = diam(H † t ) = s∈L(T H † t ) c(s) (9)
We now investigate the relationship between this diameter and α t . Consider the subtree T H † t of policy class H † t , represented schematically in Figure 4 using a black continuous outline (this subtree has a branching factor of N ). We are thus interested in finding an upper bound for s∈L(T

H † t
) c(s) as a function of α t . Consider the tree T hst , as introduced earlier in the definition of n(s), which is included in T H † t and is the same for any h ∈ H † t . To see this, recall that s t maximizes c among the leaves of T H † t . Since additionally c strictly decreases along paths, any node with a contribution larger than c(s t ) must be above these leaves, and this holds for any h ∈ H † t . Denote in this context T hst more simply by T ′ , shown in gray in the figure, and its leaves by L ′ , shown as a gray outline. Denote the children of L ′ by L ′′ , shown as a dashed line.

T '

L" L' Recall that for any h and s ∈ T h , s ′ ∈C(s,h(s)) c(s ′ ) = γc(s). This also means the sum of contributions for the leaves of any subtree of T h having some s as its root is smaller than c(s). Using these properties, we have:

x t T H t †
s∈L(T H † t ) c(s) ≤ s ′ ∈L ′ c(s ′ ) = 1 γ s ′′ ∈L ′′ c(s ′′ ) ≤ 1 γ s ′′ ∈L ′′ c(s t ) ≤ 1 γ N |L ′ | c(s t ) ≤ 1 γ N n(s t )c(s t ) = N γ α t
where we additionally exploited the facts that c(s ′′ ) ≤ c(s t ) (otherwise s ′′ would have been in T ′ ), that each node in L ′ has N children in L ′′ , and that by the definition of n(s) |L ′ | ≤ n(s t ). From this and also (9), the desired intermediate result ( 7) is obtained.

Using now ( 8) and ( 7), as well as Lemma 5, we have:

R n = max u Q * (x 0 , u) -Q * (x 0 , H * n (s 0 )) ≤ v * -ν(H * n ) ≤ b(H † t * ) -ν(H † t * ) = diam(H † t * ) ≤ N γ α *
where H * n (s 0 ) is the action chosen by OP at the root (i.e., in state x 0 ), and t * ∈ arg min t=0,...,n-1 α t . The first inequality is true because max

u Q * (s 0 , u) = v * and Q * (s 0 , H * n (s 0 )) ≥ ν(H * n ) (the return Q * (s 0 , H * n (s 0 )
) is obtained by choosing optimal actions below level 0, whereas H * n may make other suboptimal choices). The proof is complete.

Lemma 7. All nodes expanded by the algorithm belong to S α * , so that n ≤ |S α * |.

Proof. We show first that s t ∈ S αt at any iteration t. Condition (i) in the definition (5) of S αt is immediately true. For condition (ii), an N γ α t -optimal policy h whose tree T h contains s t is needed. Choose any h ∈ H † t , then s t ∈ T h and:

v * -v(h) ≤ b(H † t ) -ν(H † t ) = diam(H † t ) ≤ N γ α t
where we used some of the inequalities derived in the proof of Lemma 6. Thus s t ∈ S αt . Furthermore, α * ≤ α t implies S αt ⊆ S α * , and we are done.

Proof of Theorem 1. Exploiting Lemma 7 in combination with (6):

• if β > 0, n = Õ(α * -β ), thus for large n, α * = Õ(n -1 β ); • if β = 0, n ≤ a log 1 α * b , thus α * ≤ exp[-( n a ) 1 b ].
By Lemma 6, R n ≤ N γ α * which immediately leads to the desired results.

Proofs for values of β in special cases

Proof of Proposition 2 (uniform case). We study the size of S ε . Due to the equal rewards all the policies are optimal, and condition (ii) in (5) does not eliminate any nodes. The contribution of a node is c s) . This also means that, for any policy h, the tree T hs consists of all the nodes s ′ up to the depth of s. The number of leaves of this tree is N d(s) (recall that a policy tree has only branching factor N ), and since this number does not depend on the policy, n(s) is also N d(s) . Therefore,

(s) = P(s) γ d(s) 1-γ = ( γ N ) d(s) 1 1-γ since the probability of reaching a node at depth d(s) is ( 1 N ) d(
α(s) = n(s)c(s) = γ d(s)
1-γ and condition (i) eliminates nodes with depths larger than D = log ε(1-γ) log γ

. The remaining nodes in the whole tree, with branching factor N K, form S ε , which is of size:

|S ε | = O((N K) D ) = O((N K) log ε(1-γ) log γ ) = O(ε -log N K log 1/γ )
yielding for β the value:

β unif = log N K log 1/γ . So, for large n the regret R n = Õ(n -log 1/γ log N K ).
In fact, as can be easily checked by examining the proof of Theorem 1, the logarithmic component disappears in this case and

R n = O(n -log 1/γ log N K ) .
Proof of Proposition 3 (structured rewards). Since α(s) depends only on the probabilities, condition (i) leads to the same D = log ε(1-γ) log γ as in the uniform case. However, now condition (ii) becomes important, so to obtain the size of S ε , we must only count near-optimal nodes up to depth D.

Consider the set of nodes in T ∞ which do not belong to the optimal policy, but lie below nodes that are at depth d ′ on this policy. An example is enclosed by a dashed line in Figure 3, where d ′ = 1. All these nodes are sub-optimal to the extent of the loss incurred by not choosing the optimal action at their parent, namely: ( γ N ) d ′ 1 1-γ . Note these nodes do belong to a policy that is near-optimal to this extent, one which makes the optimal choices everywhere except at their parent. Looking now from the perspective of a given depth d, for any m ≤ d there are N d K m nodes at this depth that are (

γ N ) d-m 1 1-γ -optimal. Condition (ii), written ( γ N ) d-m 1 1-γ ≤ N γ γ d 1-γ , leads to m ≤ d log N log N/γ + 1. Then: |S ε | ≤ D d=0 N d K d log N log N/γ +1 ≤ K D d=0 N K log N log N/γ d If N > 1: |S ε | = O N K log N log N/γ ) D = O (N K log N log N/γ ) log ε(1-γ) log γ = O ε -log N log 1/γ (1+ log K log N/γ )
yielding the desired value of β rew = log N log 1/γ (1+ log K log N/γ ). If N = 1 (deterministic case), β rew = 0 and:

|S ε | = D d=0 1 • K = (D + 1)K = log ε(1 -γ) log γ + 1 K ≤ a log 1/ε
for small ε and some constant a, which is of the form (6) for b = 1. From Theorem 1, the regret is O(exp(-n a )).

Proof of Proposition 4 (structured probabilities). We will show that the quantities of nodes with sizable contributions on the subtree of one policy, and respectively on the whole tree, satisfy:

n(λ) = |{s ∈ T ∞ | c(s) ≥ λ }| = Õ(λ -δ ) n h (λ) = |{s ∈ T h | c(s) ≥ λ }| = Õ(λ -δ h )
for constants δ h and δ; and we will find values for these constants. (Note n h (λ) is not a function of h, since all policies have the same probability structure.) Then, since condition (ii) always holds and nodes in S ε only have to satisfy condition (i):

|S ε | = |{s ∈ T ∞ | n(s)c(s) ≥ ε }| ≤ |{s ∈ T ∞ | n h (c(s))c(s) ≥ ε }| ≤ s ∈ T ∞ a[log 1/c(s)] b c(s) 1-δ h ≥ ε = Õ(ε -δ 1-δ h )
where we used n(s) ≤ n h (c(s)) and n h (c(s)) = Õ(c(s) -δ h ). Thus β = δ 1-δ h . Consider now n h (λ). The nodes at each depth d correspond to a binomial distribution with d trials, so there are C m d nodes with contribution c(s) = p d-m (1p) m γ d 1-γ , for m = 0, 1, . . . , d. Since these contributions decrease monotonically with d, as well as with m at a certain depth, condition c(x) ≥ λ eliminates all nodes above a certain maximum depth D, as well as at every depth d all nodes above a certain m(d), where: leading to the value for δ h = log η ′ log 1/(pγ) .3

Similarly, it is shown that n(λ) = Õ(λ -log Kη ′ log 1/(pγ) ) and thus δ = log Kη ′ log 1/(pγ) , where the extra K comes from the fact we count the nodes corresponding to all K d policies rather than just one.

The desired result is immediate:

β prob = δ 1-δ h = log Kη ′
log 1/(pγη ′ ) . Note throughout, we silently used the fact that p is close to 1; indeed, this is required for some of the steps to be meaningful, such as having log 1/(pγη ′ ) > 0.

  Appearing in Proceedings of the 15 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2012, La Palma, Canary Islands. Volume XX of JMLR: W&CP XX. Copyright 2012 by the authors.

Figure 1 :

 1 Figure 1: Illustration of an OP tree after three expansions, for N = K = 2. The squares are state nodes labeled by states x, and the actions u are explicitly included as circle, choice nodes. Transition arcs to next states are labeled by probabilities p and rewards r. The dashed outline encloses a possible optimistic subtree.

  ure 3. So, there is a "maximal" amount of structure in the reward function.

Figure 3 :

 3 Figure3: Illustration of a planning tree for structured rewards, up to depth 2, for N = K = 2. Thick lines: subtree of optimal policy, where each transition is associated with a reward of 1. Thin lines: the rest of the tree, associated with 0 rewards.

Figure 4 :

 4 Figure 4: Tree of the optimistic policy class and various subtrees.

  Note in the condition for D we set m = 0 to obtain the largest probability. So, m(d) decreases linearly with d, so that up to some depth m * , m(d) ≥ d and we count all the nodes up to m = d; while above m * , m(d) < d and we count fewer nodes. The depth m * is obtained by solving m(d) = d, leading to m * = log 1/(λ(1-γ))log 1/(γ(1-p)) = log 1/(pγ) log 1/(γ(1-p)) D = ηD with the notation η = log 1/(pγ) log 1/(γ(1-p)) . The structure of the subtree satisfying c(s) ≥ λ is represented in Figure5.

Figure 5 :.

 5 Figure 5: Schematic representation of the subtree satisfying c(s) ≥ λ, shown in gray. Nodes with larger probabilities are put to the left. The thick line represents the fringe m(d) where nodes stop being counted.

More generally, f (x) is Õ(g(x)) if f (x) ≤ a(log g(x)) b g(x)for some a, b > 0. This is usually understood to hold for all x, so when it only holds for large/small values of x, we explicitly mention this restriction.

The definition of n(s) in fact only requires counting the leaves of the subtree corresponding to n h (λ) (thick line in Figure5), while we counted all the nodes (gray area). Exploiting this property is unlikely to be helpful, however, since in the upper bound derived for n h (λ) the inner term in the sum (corresponding to C m d , the number of nodes having a certain probability) is dominant. The fact that the whole tree is taken into account only enters the logarithmic component of the bound.

Acknowledgements

This research was financially supported by the French National Research Agency (ANR) under project EXPLO-RA, and by the European Community's Seventh Framework Programme under grant no. 231495 (Complacs project). We also wish to thank the reviewers for their comments, which greatly helped to improve the paper.