Pierre-Arnaud Coquelin
email: coquelin@cmapx.polytechnique.fr

Rémi Munos
email: remi.munos@inria.fr

Bandit Algorithms for Tree Search

, is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is "over-optimistic" in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT using a confidence sequence that scales exponentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account actual smoothness of the rewards for performing efficient "cuts" of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly infinite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illustrate these methods on a global optimization problem of a continuous function, given noisy values.

Introduction

Bandit algorithms have been used recently for tree search, because of their efficient trading-off between exploration of the most uncertain branches and ex-ploitation of the most promising ones, leading to very promising results for dealing with huge trees (see e.g. the go program MoGo in [START_REF] Gelly | Modication of UCT with patterns in Monte-Carlo go[END_REF]). In this paper we focus on bandit algorithms based on Upper Confidence Bounds (UCB) [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] applied to tree search, such as UCT (Upper Confidence Bounds applied to Trees) [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF]. This general bandit-based procedure for tree search is defined by Algorithm 1; the core issue being the way the upper-bounds B i,p,ni on the value of each node i are maintained. A trajectory is a sequence of nodes from the root to a leaf, where at each node i, the next node is chosen as the (or one) child having the highest B value among its children C(i). A reward is received at the leaf. After a trajectory is run, the number of visits n i of each node i in the trajectory are incremented.

For example, in the case of UCT, the upper-confidence bound of a node i is:

B i,p,ni def = X i,ni + 2 log(p) n i . (1)
where n i (resp. p) is the number of times this node (resp. its parent) has been visited, and X i,ni is the empirical mean of the rewards that have been obtained by trajectories going through that node.

In this paper we consider a max search in a binary tree (i.e. there are 2 actions from each node) of depth D. The extension to more actions is straightforward.

At each leaf i is assigned a random variable X i , with bounded support included in [0, 1], whose law is unknown.

We write I t the chosen leaf at round t (i.e. obtained at the end of the t-th trajectory). Successive visits of the leaves (I t ) yield a sequence of independent and identically distributed (i.i.d.) samples x t ∼ X It , called rewards, or payoffs. We write x i,t the t-th reward received at a leaf i.

The value of a leaf i is the expected reward: µ i def = EX i . Now we define the value of any node i as the maximal value of the leaves in the sub-tree (branch) starting from node i. An optimal leaf is a leaf having the largest expected reward. We will denote by * quantities related to an optimal node. For example µ * denote the maximal value of the leaves, i.e. the value of the root. One possible goal is to compute µ * . Another goal is to find an optimal branch, i.e. a sequence of nodes from the root to an optimal leaf. Let i * be an optimal leaf. We write n i (t) the random variable that counts the number of times a node i has been visited up to time t. Thus

x t = x It,nI t (t) .
We define the cumulative regret up to time n as the loss in the cumulative rewards resulting from choosing sub-optimal leaves instead of an optimal one:

R n def = n t=1 x i * ,n i * (t) - n t=1 x t .
We also define the cumulative pseudo-regret:

Rn def = nµ * - n t=1 µ It = j∈L n j ∆ j ,
where L is the set of leaves and ∆ j def = µ * -µ j . The difference between the regret and the pseudo-regret comes from the randomness of the rewards.

In tree search, our goal is thus to find an exploration policy of the branches such as to minimize the regret, in order to select an optimal leaf as fast as possible. Notice that thanks to Wald's theorem, the regret and pseudo-regret have the same expectation: ER n = E Rn . Now, thanks to a contraction of measure phenomenon, the regret per round R n /n turns out to be very close to the pseudo-regret per round Rn /n. Indeed, using Azuma's inequality for martingale difference sequences (see Proposition 1), with probability at least 1 -β, we have at time n,

|R n -Rn | ≤ |Sub(n)| log(2/β)/2, (2)
where |Sub(n)| is the cardinal of Sub(n) def = {t ∈ {1, . . . , n}, I t = i * }, the set of times t, up to time n, when the chosen leaf I t is different from i * .

The fact that R n -Rn is a martingale difference sequence comes from the property that the chosen leaf at time t is entirely determined by the filtration F t-1 (defined by the random samples up to time t-1). Thus

E[x t |F t-1 ] = µ It and Rn -R n = t∈Sub(n) x t -µ It with E[x t -µ It |F t-1 ] = 0,
and (2) follows from Proposition 1. Hence, in this paper, we will focus on providing high probability bounds on the pseudo-regret, and on the number of sampled sub-optimal leaves. Bounds on the regret directly follow from (2).

The paper is organized as follows. First, we analyze the UCT algorithm defined by the upper confidence bound [START_REF] Audibert | Variance estimates and exploration function in multi-armed bandit[END_REF]. We show that its behavior is risky and may lead to a regret (expressed in terms of the depth D of the tree) as bad as Ω(exp(• • • exp(1) • • • )) (there are D -1 composed exponential functions). If we modify the algorithm by using an increased exploration sequence, defining:

B i,p,ni def = X i,ni + √ p n i , (3)
we obtain an improved worst-case behavior compared to regular UCT, but the regret may still be as bad as Ω(exp(exp(D))) (see Section 2). We then propose in Section 3 a modified UCT based on the bound (3), where the confidence interval is multiplied by a factor that scales exponentially with the horizon depth.

Next, we analyze the Flat-UCB algorithm, which simply performs UCB directly on the leaves.

In Section 5 we introduce the Bandit Algorithm for Smooth Trees (BAST), which takes into account actual smoothness of the rewards for performing efficient "cuts" of branches that are (with high confidence) suboptimal, without having to explore all the leaves of these branches. This is our main contribution. We analyze the regret and show the improvement over both UCT and Flat-UCB. We provide a numerical experiment for the problem of optimizing a continuous function given noisy values.

Finally, in Section 6 we extend and analyze BAST using an incremental tree expansion procedure, which applies when the tree is so big that its full representation in memory is impossible. We show that this method builds an asymmetric tree that indefinitely develops the optimal branch only.

Preliminaries and additional notations Let L denotes the set of leaves and S the set of sub-optimal leaves. For any node i, we write L(i) the set of leaves that belong to the sub-tree starting from node i. When there is no possible confusion, we write n i instead of n i (n) the number of times a node i has been visited up to time n. For a leaf j, we define the empirical mean of the rewards obtained at j:

X j,nj def = 1 n j nj t=1
x j,t . Now, for any node i, we defined the empirical mean of the rewards obtained from i, up to time n:

X i,ni def = 1 n i ni t=1 x i,t = 1 n i j∈L(i) n j X j,nj ,
and the empirical mean of the values of the leaves:

Xi,ni def = 1 n i j∈L(i) n j µ j .
We finally remind Azuma's inequality (see [START_REF] Györfi | A Probabilistic Theory of Pattern Recognition[END_REF]): Then for every ǫ > 0,

Proposition 1. Let Y 1 , Y
P( n t=1 Y t ≥ ǫ ≤ 2e -2ǫ 2 / P n t=1 d 2 t .
2 Regret lower bound for UCT

Notice that the bound (1) used in UCT comes from a concentration inequality that applies when the rewards are independent and identically distributed. However, in the tree problem, the received rewards at each node do not satisfy these assumptions because the chosen leaves depend on a non-stationary node selection process. Hence, the bound (1) may not be a true upper confidence bound of the nodes value.

Nevertheless, as argued in [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF], since the confidence interval term increases with log(p) when a child node is not chosen, all children from each node will eventually be indefinitely visited. Then, using an inductive argument on the depth, it is proven that, after a transitory period of time N 0 , only the optimal branch will be followed, yielding an expected regret of order O(N 0 + log(n)). However, this "transitory" phase may last very long. Indeed, consider the example shown in Figure 1. The rewards are deterministic and for a node of depth d in the optimal branch (obtained after choosing d times action 1), if action 2 is chosen, then a reward of D-d D is received (all leaves in this branch have the same reward). If action 1 is chosen, then this moves to the next node in the optimal branch. At depth D -1, action 1 yields reward 1 and action 2, reward 0. We assume that when a node is visited for the first time, the algorithm starts by choosing action 2 before choosing action 1. D . The optimal branch consists in choosing always action 1, which yields reward 1. In the beginning, the algorithm believes the arm 2 is the best, spending most of its times exploring this branch (as well as all other sub-optimal branches). It takes Ω(exp(. . . (exp(1)) . . . )) (D -1 times) rounds to get the 1 reward! We now establish a lower bound on the number of times suboptimal rewards are received before getting the optimal 1 reward for the first time. Write n the first time the optimal leaf is reached. Write n d the number of times the node (also written d making a slight abuse of notation) of depth d in the optimal branch is reached. Thus n = n 0 and n D = 1. At depth D -1, we have n D-1 = 2 (since action 2 has been chosen once in node D -1).

We consider both the logarithmic confidence sequence used in (1) and the square root sequence in [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF]. Let us start with the square root confidence sequence (3). At depth d -1, since the optimal branch is followed by the n-th trajectory, we have (writting d ′ the node resulting from action 2 in the node d -1):

X d ′ ,n d ′ + √ n d-1 n d ′ ≤ X d,n d + √ n d-1 n d . But X d ′ ,n d ′ = (D -d)/D and X d,n d ≤ (D-(d+1))/D since the 1 reward has not been received before. We deduce that 1 D ≤ √ n d-1
n d . Thus for the square root confidence sequence, we have

n d-1 ≥ n 2 d /D 4 . Now, by induction, n ≥ n 2 1 D 4 ≥ n 2 2 2 D 4(1+2) ≥ n 2 3 3 D 4(1+2+3) ≥ • • • ≥ n 2 D-1 D-1 D 2D(D-1) Since n D-1 = 2, we obtain n ≥ 2 2 D-1 D 2D(D-1)
. This is a double exponential dependency w.r.t. D. For example, for D = 20, we have n ≥ 10 156837 . Thus the transitory phase lasts N 0 = Ω(exp(exp(D))), and the regret is Ω(exp(exp(D))) + O(log n), showing a double exponential dependency w.r.t. the depth of the tree. Now, the usual logarithmic confidence sequence defined by (1) yields an even worst lower bound on the regret since we may show similarly that

n d-1 ≥ exp(n d /(2D 2 )) thus n = Ω(exp(exp(• • • exp(1) • • • ))) (composition of D -1 exponential functions). Thus UCT algorithm has a regret Ω(exp(exp(• • • exp(1) • • • ))) + O(log(n)),
showing a hyperexponential dependency w.r.t. D.

The reason for this bad behavior is that the algorithm is too optimistic (it does not explore enough and may take a very long time before discovering good branches that looked initially bad) since the bounds (1) and ( 3) are not true upper bounds on the nodes value, at least during the transitory period which may last very long.

Modified UCT

We modify the confidence sequence in order to explore more the nodes that are closer to the root than the leaves, taking into account the fact that the time needed to decrease the bias (µ i -Xi,ni ) at a node i of depth d increases with the depth horizon (D -d). For such a node i of depth d, we define the upper confidence bound:

B i,ni def = X i,ni + (k d + 1) log(β -1 ni ) 2n i + k ′ d n i , (4)
where

β n def = β 2N n(n+1) with N def = 2 D+1
-1 the number of nodes in the tree, and the coefficients:

k d def = 1 + √ 2 √ 2 (1 + √ 2) D-d -1 (5) k ′ d def = (3 D-d -1)/2
Notice that we used a simplified notation, writing B i,ni instead of B i,p,ni since the bound does not depend on the number of visits of the parent's node.

We now provide a high probability bound on the regret which is exponential in the depth D and is square root dependent on n. The proof is given in [START_REF] Coquelin | Bandit algorithms for tree search[END_REF].

Theorem 1. Let β > 0. Consider Algorithm 1 with the upper confidence bound (4). Then, with probability at least 1 -β, for all n ≥ 1, the pseudo-regret is bounded by

Rn ≤ 1 + √ 2 2 (1 + √ 2) D -1 log(β -1 n )n + 3 D -1 2
The confidence intervals used in (4) are actually chosen such that the B values represent true upper confidence bounds on the nodes value, i.e. with high probability (at least 1-β), for all node i, for all

n i ≥ 1, µ i ≤ B i,ni .
Thus this procedure is safe, which prevents us from having bad behaviors for which the regret could be disastrous, like in regular UCT. However, contrarily to regular UCT, in good cases, the procedure does not adapt to the effective smoothness in the tree. For example, at the root level, the confidence interval is O(exp(D)/ √ n) which leads to sampling almost uniformly both actions for a time O(exp(D)). Thus, if the tree were to contain 2 branches, one only with zeros, one only with ones, this smoothness would not be taken into account by this method, and the regret would still be O(exp(D)

√ n). Thus modified UCT is less optimistic than regular UCT but safer in a worstcase scenario.

Flat UCB

A method that would combine both the safety of modified UCT and the adaptivity of regular UCT is to consider a regular UCB algorithm on the leaves. Such a flat UCB could naturally be implemented in the tree structure by defining the upper confidence bound of a non-leaf node as the maximal value of the children's bound:

B i,ni def = X i,ni + log(β -1 n i ) 2ni if i is a leaf, max j∈C(i) B j,nj otherwise. ( 6
)
where we use

β n def = β 2 D+1 n(n+1)
. We deduce: Theorem 2. Consider the flat UCB defined by Algorithm 1 and (6). Then, with probability at least 1 -β, the pseudo-regret is bounded by a constant independent of n:

Rn ≤ 6 i∈S 1 ∆ i log( 2 D+2 ∆ 2 i β ) ≤ 6 2 D ∆ log( 2 D+2 ∆ 2 β ),
where

∆ def = min i∈S ∆ i .
Proof. Consider the event E under which, for all leaves i, for all n ≥ 1, we have

|X i,n -µ i | ≤ c n , with the confidence intervals c n = log(β -1 n ) 2n
. Then the event E holds with probability at least 1 -β. Indeed, from a union bound argument, there are at most 2 D Chernoff-Hoeffding's inequalities (one for each leaf) of the form:

P (|X i,n -µ i | ≤ c n , ∀n ≥ 1) ≥ 1 - n≥1 2β n = 1 - β 2 D .
Under the event E, we now provide a regret bound by bounding the number of times each sub-optimal leaf is visited. Let i ∈ S be a sub-optimal leaf. Write * an optimal leaf. If, at some round n, the leaf i is chosen, this means that X * ,n * + c n * ≤ X i,ni + c ni . Using the (lower and upper) confidence interval bounds for leaves i and * , we deduce that µ * ≤ µ i + 2c ni . Thus

∆i 2 2 ≤ log(β -1 n i ) 2ni
. Hence, for all n ≥ 1, n i is bounded by the smallest integer n 0 such that

n0 log(β -1 n 0 ) > 2/∆ 2
i . An upper bound on n 0 may be found by analyzing the zero of the function x → x -w log(2 D+1 x(x + 1)β -1 ), writing w = 2/∆ 2 i . A rough bound on n 0 is 3w log(w2 D+1 β -1 ). We deduce that the number of times a leaf i is chosen is at most

n i ≤ 6 ∆ 2 i log( 2 ∆ 2 i 2 D+1 β -1 ).
The bound on the regret follows immediately from the property that Rn = i∈S n i ∆ i .

This algorithm is safe in the sense that with high probability, the bounds defined by ( 6) are true upper bounds on the value on the leaves. However, since there are 2 D leaves, the regret still depends exponentially on the depth D.

In the next section, we introduce another UCB-based algorithm that takes into account possible smoothness of the rewards to process efficient "cuts" of suboptimal branches with high confidence.

Bandit Algorithm for Smooth Trees

We would like to exploit the fact that if the leaves of a branch have similar values, then a confidence interval on the value of that branch may be made much tighter than the maximal confidence interval of its leaves (as processed in the Flat UCB). Indeed, assume that from a node i, all leaves j ∈ L(i) in the branch i have values µ j , such that µ i -µ j ≤ δ. Then,

µ i ≤ 1 n i j∈L(i) n j (µ j + δ) ≤ X i,ni + δ + Xi,ni -X i,ni ,
and thanks to Azuma's inequality, the term Xi,ni -X i,ni is bounded with probability 1-β by a confidence interval log(2β -1 ) 2ni which depends only on n i (and not on n j for j ∈ L(i)). We now make such a smoothness assumption either along an optimal path only or along any almost optimal path. Assumption A * : for any depth d < D, there exists δ d > 0, such that for (at least) one optimal node i of depth d (i.e. such that µ i = µ * ), we have, for all leaves j ∈ L(i) in the branch i, µ * -µ j ≤ δ d .

A stronger assumption requires the smoothness assumption to hold for any η-optimal node i (where .

η > 0), i.e. when i ∈ I η def = {node i, ∆ i ≤ η}.
We now provide high confidence bounds on the number of times each sub-optimal node is visited.

Theorem 3. Assume A * . Let I denotes the set of nodes i such that ∆ i > δ di , where d i is the depth of node i. Define recursively the numbers N i associated to each node i of a sub-optimal branch (i.e. for which ∆ i > 0):

-If i is a leaf, then N i def = 6 log(4N β -1 /∆ 2 i ) ∆ 2 i . -It i is not a leaf, then N i def = N i1 + N i2 , if i / ∈ I min(N i1 + N i2 , 6 log(4N β -1 /(∆i-δ d i ) 2 ) (∆i-δ d i ) 2
), if i ∈ I

where i 1 and i 2 denote the children nodes of i. Then, with probability 1 -β, for all n ≥ 1, for all sub-optimal nodes i, we have n i ≤ N i .

Proof. We consider the event E under which |X i,n -Xi,n | ≤ c n for all nodes i and all times n ≥ 1. Like in the previous result, the confidence interval

c n = log(2N n(n+1)β -1 ) 2n is chosen such that P (E) ≥ 1 -β.
Under E, the smoothness assumption along an optimal path implies that for any optimal node * in this branch, B * ,n * is a true upper bound on µ * , i.e. µ * ≤ B * ,n * . Now, for any sub-optimal leaf i, using the same analysis as in Flat UCB, we deduce the bound n i ≤ N i . Then, by backward induction on the depth, assume that n i ≤ N i for all sub-optimal nodes of depth d + 1. Let i be a node of depth d.

Then n i ≤ n i1 + n i2 ≤ N i1 + N i2 .
i ≤ 6 log(4N β -1 /(∆i-δ d ) 2 ) (∆i-δ d ) 2
. Thus n i ≤ N i at depth d, which finishes the inductive proof. Now we would like to compare the regret of BAST to that of Flat UCB. First, we expect a direct gain for nodes i ∈ I. Indeed, from the previous result, whenever a node i of depth d is such that ∆ i > δ d , then this node will be visited, with high probability, at most O(1/(∆ i -δ d ) 2 ) times (neglecting log factors), independently of the number of leaves (2 D-d ) in the branch starting from i. But we also expect an improved bound on n i whenever ∆ i > 0 if at a certain depth h ∈ [d, D], all nodes j of depth h in the branch i satisfy ∆ j > δ h .

The next result enables to further analyze the expected improvement over Flat UCB. Theorem 4. Let η > 0. Write J η def = I η ∩ L the set of η-optimal leaves. Assume A η with an exponential sequence δ d = δγ d . Then, with probability at least 1β, the pseudo regret satisfies, for all n ≥ 1,

Rn ≤ i∈Jη,∆i>0 6 ∆ i log( 4N ∆ 2 i β ) + 54(3δ) c η 2+c log( 4N η 2 β ) ≤ 6|J η | 1 ∆ log( 4N ∆ 2 β ) + 54(3δ) c η 2+c log( 4N η 2 β ) (8)
where

c def = log(2)/ log(1/γ).
The first term in the bound is the same as for Flat UCB, but the sum is performed only on the leaves i ∈ J η whose value is η-close to optimality. The second term is O(1/η 2+c ) depends weakly (linearly) on the depth D (through log(N )). Thus, if η is fixed and we increase the depth D of the tree, the first term is dominant and we expect an important regret reduction compared to Flat UCB when the number |J η | of ηoptimal leaves is small compared to the total number of leaves 2 D .

Notice that this bound (8) has no explicit exponential dependency w.r.t. the depth D. However the 1/∆ term is of order O(1/γ D ) from our smoothness assumption.

Proof. We consider the same event E as in the proof of Theorem 3. Let h be the smallest integer such that δ h ≤ η/3. We have h ≤ log(3δ/η) log(1/γ) +1. Let i be a node of depth h. If i ∈ I 2η/3 , then, thanks to the assumption A η , we have for all j ∈ L(i), µ j ≥ µ i -η/3 ≥ µ * -η, thus j ∈ J η . Now, if i / ∈ I 2η/3 , then using similar arguments as in Theorem 3, the number of times n i this node is visited is at most

n i ≤ 6 log(4N β -1 /(∆i-δ h ) 2 ) (∆i-δ h ) 2 , but since ∆ i -δ h ≥ 2η/3 -η/3 ≥ η/3, we have: n i ≤ l/η 2 , writing l = 54 log(4N β -1 /η 2 ).
Since there are 2 h nodes of depth h, the number of times that nodes of depth h that do not belong to I 2η/3 are chosen is bounded by

2 h l η 2 ≤ 2 3δ η log(2) log(1/γ) l η 2 = 2l(3δ) c η c+2
The pseudo regret is bounded by the sum for all η-optimal leaves i ∈ J η of n i ∆ i (with

n i ≤ 6 ∆ 2 i log( 4N β -1 ∆ 2 i
) like in Theorem 2) plus the number of times nodes i of depth h such that i / ∈ I 2η/3 are chosen:

Rn ≤ i∈Jη ,∆i>0 6 ∆ i log( 4N ∆ 2 i β ) + 54(3δ) c η 2+c log( 4N η 2 β ).
which ends the proof.

Remark 1. Notice that if we choose δ = 0, then BAST algorithm reduces to regular UCT (with a slightly different confidence interval), since in that case, the min in [START_REF] Györfi | A Probabilistic Theory of Pattern Recognition[END_REF] gives the bounds

B i,ni = X i,ni + c ni . Now if δ = ∞, then the bounds is B i,ni = max j∈C(i) B j,nj
, which is simply Flat UCB. Thus BAST may be seen as a generic UCB-based bandit algorithm for tree search, that allows to take into account actual smoothness of the tree, if available.

Numerical experiments: global optimization of a noisy function. We search the global optimum of an [0, 1]-valued function, given noisy values. This is a continuum-armed bandit problem (see e.g. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF]). The domain

[0, 1] is uniformly discretized into 2 D intervals [ j 2 D , j+1 2
D ] 0≤j<2 D (of center y j ), each one related to a leaf j of a tree of depth D. The tree implements a recursive binary splitting of the domain, each node of depth d corresponding to an interval of size 2 -d . At time t, if the algorithm selects a leaf j, then the (binary) reward x t i.i.d.

∼ B(f (y j )), a Bernoulli random variable with parameter f (y j ) (i.e. P (x t = 1) = f (y j ), P (x t = 0) = 1 -f (y j )).

If we assume that f is Lipschitz (with Lipschitz constant L), then the exponential smoothness assumption δ d = δγ d holds for all nodes with δ = L/2 and γ = 1/2 (thus c = 1). In the experiments, we used the function

f (x) def = max 3.6x(1-x), 1-1 a |1-a-x|
, where a > 0, which is plotted in Figure 2 for a = 0.1. Note that an immediate upper bound on the Lipschitz constant of f is L = 1/a. BAST concentrates its ressources on the good leaves: In Figure 2 we show the proportion n j /n of visits of each leaf j. We observe that, when n increases, the proportion of visits concentrates around the global maximum. We now compare the regret of Flat UCB, UCT and BAST algorithms for a = 0.01, which exhibits a function that possess a broad local optimal bump and a very picky global optimum. Figure 3 shows the cumulative regret per round R n /n (for n = 10 7 ) for BAST used with different values of the smoothness constant δ. Starting from δ = 0 (which corresponds to UCT with a slightly different confidence interval), the regret is poor. This holds also for regular UCT with the confidence interval defined by [START_REF] Audibert | Variance estimates and exploration function in multi-armed bandit[END_REF]. This happens because the algorithm gets stuck in the local optimum, as illustrated in Section 2. When δ increases, the regret decreases (the global optimum of f is reached) first, and then increases again, because the "cuts" performed by BAST are less and less frequent. For an infinite value of δ (which corresponds to Flat UCB) the regret is 0.23.

We observe that BAST with δ = L/2 = 1/(2a) = 50 (which corresponds to the Lipschitz smoothness of f ) outerforms both UCT and Flat UCB. The optimal performance is actually reached for a value 0 < δ < 50.

Remark 2. If we know in advance that the function is locally smooth around its maximum, then one may use a smaller value of γ. For example, if the function is locally quadratic, then δ d = δγ d would hold for γ = 1/4 and appropriate δ. This would cut more efficiently sub-optimal branches and yield improved performance (compared to γ = 1/2). Thus any a priori knowledge about the tree smoothness around optimality could be taken into account in the BAST bound [START_REF] Györfi | A Probabilistic Theory of Pattern Recognition[END_REF].

Growing trees

If the tree is too big (possibly infinite) to be represented, one may wish to discover it sequentially, exploring it at the same time as searching for an optimal value. We propose an incremental algorithm similar to the method described in [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF] and [START_REF] Gelly | Modication of UCT with patterns in Monte-Carlo go[END_REF]: The algorithm starts with only the root node. Then, at each stage n, it chooses which leaf, call it i, to expand next. Expanding a leaf means turning it into a node i, and adding in our current tree representation its children leaves i 1 and i 2 , from which a reward (one for each child) is received. The process is then repeated in the new tree. Such an iterative growing tree requires a amount of memory O(n) linear in the number of rounds.

Here, the tree is such that the value of each node i is the maximum of the values of its children. Besides, the A * assumption says that from any optimal leaf * of depth d, the received reward x n ∈ [0, 1] at time n is a random variable whose expected value satisfies:

µ * -E[x n |F n-1 ] ≤ δ d .
Notice that we only make an assumption on the expectation of x n , and not on its specific value at time n. Theorem 5. Assume A * . Consider this incremental tree method using Algorithm 1 defined by the bound [START_REF] Györfi | A Probabilistic Theory of Pattern Recognition[END_REF] with the confidence interval of a node i of depth d:

c d,ni def = log(2 2d+1 n i (n i + 1)β -1 ) 2n i .
Then, with probability 1 -β, for any sub-optimal node i (of depth d), i.e. s.t. ∆ i > 0, we have:

n i ≤ 6 log(2 2d+2 β -1 /(∆ i -δ d ) 2 ) (∆ i -δ d ) 2 , if ∆ i > δ d , ≤ 3 2 δ c c 2 + c ∆ i c+2 log 2 2d β (2 + c) 2 ∆ 2 i 2 -d , otherwise.
Hence, any sub-optimal branch is visited a finite number of times. Thus, the number of trajectories that do not follow an optimal path up to a given depth is finite. Thus this algorithm expands indefinitely the optimal branches only. .

Otherwise, let h be a depth such that δ h < ∆ i (thus h > d). This is satisfied for all integer h ≥ log(δ/∆i) log(1/γ) . Similarly, we deduce that the number of times n j a node j of depth h has been visited is bounded by 6 log(2 2d+2 β -1 /(∆ i -δ h ) 2 )/(∆ i -δ h ) 2 . Thus i has been visited at most

n i ≤ min h≥ log(δ/∆ i ) log(1/γ) 2 h-d 6 log(2 2d+2 β -1 /(∆ i -δ h ) 2 ) (∆ i -δ h ) 2 .
This function is minimized (neglecting the log term) for h = log( δ(2+c) c∆i )/ log(1/γ), which leads to the second bound.

For illustration, Figure 4 shows the tree obtained when applied to the function optimization problem of previous section. This algorithm develops the tree in an asymmetric way, expanding in depth the optimal branch, leaving mainly unexplored sub-optimal branches.

Conclusion

BAST enables to take into account possible smoothness in the tree to perform efficient "cuts" 1 of suboptimal branches, with high probability. Numerically, in all the problems we considered, BAST performed better than both UCT and Flat UCB for an appropriate smoothness coefficient δ ∈ (0, ∞). Experimental work seems to be necessary to obtain the best coefficient. However, if any additional smoothness of the optimal branch is provided, the smoothness sequence in the bound (7) may be refined, leading to improved performance. The use of variance estimate (see e.g. 1 Note that this term may be misleading here since the UCB-based methods described here never explicitly delete branches [1]) would tighten the confidence intervals and improve the performance too. However, it seems important to use true upper confidence bounds, in order to avoid bad cases as illustrated in regular UCT.

Extension to minimax search in 2 players, 0-sum games is possible and would yield similar results.

Algorithm 1

 1 Bandit Algorithm for Tree Search for n ≥ 1 do Run the n-th trajectory (sequence of nodes (i 0 , . . . , i D ) from the root to a leaf ): Set the current node i 0 to the root for d = 1 to D do * Compute the bounds B j,ni d-1 ,nj for all children j ∈ C(i d-1 ) of node i d-1 * Select the node i d as a child of node i d-1 that has the highest B value, i.e. i d ∈ arg max j∈C(i d-1 ) B j,ni d-1 ,nj end for Receive reward x n iid ∼ X iD end for

Figure 1 :

 1 Figure 1: A bad example for UCT. From the root (left node), action 2 leads to a node from which all leaves yield reward D-1D . The optimal branch consists in choosing always action 1, which yields reward 1. In the beginning, the algorithm believes the arm 2 is the best, spending most of its times exploring this branch (as well as all other sub-optimal branches). It takes Ω(exp(. . . (exp(1)) . . . )) (D -1 times) rounds to get the 1 reward!

Assumption A η :

 η For any i ∈ I η of depth d < D, there exists δ d > 0, such that for all j ∈ L(i), µ i -µ j ≤ δ d . Typical choices of the smoothness coefficients δ d are exponential δ d def = δγ d (with δ > 0 and γ < 1), polynomial δ d def = δd α (with α < 0), or linear δ d def = δ(D -d) (Lipschitz in the tree distance) sequences. We define the Bandit Algorithm for Smooth Trees (BAST) by Algorithm 1 with the upper confidence bounds defined, for any leaf i, by B i,ni def = X i,ni + c ni , and for any non-leaf node i of depth d, byB i,ni def = min max j∈C(i) B j,nj , X i,ni + δ d + c ni(7)with the confidence interval c n def = log(2N n(n+1)β -1 ) 2n

Figure 2 :

 2 Figure 2: Function f for a = 0.1 (plain curve) and (rescaled) proportion n j /n of leaves visitation for BAST with δ = 5, D = 10 for n = 10 4 and n = 10 6 .

Figure 3 :

 3 Figure 3: Cumulative regret per round R n /n for BAST with different values of the smoothness constant δ. The dotted curves represent +/-one standard deviation computed over 20 simulations. Here a = 0.01, n = 10 7 , D = 17.

Proof. 1 d= 2

 12 Consider the event E under which |X i,ni -Xi,ni | ≤ c d,ni for all depths d ≥ 1, for all nodes i of depth d, for all times n i ≥ 1. Write c d,ni = log(2β -2d n(n + 1)β -1 . Since d≥1 2 d i=1 ni≥1 β d,ni = β, we see that the confidence intervals c d,ni are such that P (E) ≥ 1 -β. At round n, let i be a node of depth d. If ∆ i > δ d , then similarly to the proof of Theorem 3, we have n i ≤ 6 log(2 2d+2 β -1 /(∆i-δ d ) 2 ) (∆i-δ d ) 2

Figure 4 :

 4 Figure 4: Tree resulting from the iterative growing BAST algorithm, after n = 4000 rounds, with δ = 5, a = 0.1.

  2 , • • • be a martingale difference sequence, i.e. for all t ≥ 1, E[Y t |Y 1 , . . . , Y t-1 ] = 0 with probability (w.p.) 1, and d 1 , d 2 , . . . real positive numbers such that for all t ≥ 1, 0 ≤ Y i ≤ d i w.p. 1.

  ,ni ≤ X i,ni +δ d +c ni ≤ µ i +δ d +2c ni , we deduce µ * ≤ µ i +δ d +2c ni , which rewrites ∆ i -δ d ≤ 2c ni .Using the same argument as in the proof of Flat UCB, we deduce that for all n ≥ 1, we have n

Now consider a sub-optimal node i ∈ I. If the node i is chosen at round n, the form of the bound

[START_REF] Györfi | A Probabilistic Theory of Pattern Recognition[END_REF]

implies that for any optimal node * , we have B * ,n * ≤ B i,ni . Since µ * ≤ B * ,n * and B i

Acknowledgements: Warm thanks to Jean-François Hren for running all the numerical experiments.


The Cultural Dimensions of Computer Simulation

Sebastian Grevsmühl Without a doubt, computer simulations have revolutionized our understanding of the sciences during the second half of the 20th century. From numerical weather forecasting to climate simulations, from economic modeling to social planning, computer simulations play a leading role in our understanding of various global socioeconomic, geophysical, and environmental processes. Blurring established norms and transgressing boundaries of traditional fields of science, computer simulations generate their own research logic, their own laboratory practices, as well as fundamentally new forms of knowledge. Indeed, they have helped introduce truly new norms for what counts as knowledge, stirring controversial epistemological discussions among scientists and philosophers regarding whether models can be "validated" or "verified" in a traditional sense or whether they demand a whole new epistemological framework, far beyond traditional approaches established around notions such as theory and experiment.

Reaching well beyond these important epistemological questions, an international conference was convened by the Institute for Advanced Study MECS (Media Cultures of Computer Simulation) at Leuphana University Lüneburg, Germany, in June 2015. Funded by the German Research Foundation (DFG), the two-day international conference, entitled "Dealing with Climate Change: Calculus and Catastrophe in the Age of Simulation," explored the cultural subtexts and the specific cultural conditions of computer simulation, especially in the context of ongoing debates on past and future climate change. One of the conference's leading aims was to move beyond the well-known epistemological discussions to engage in more detail in the fundamental cultural, economic, and political underpinnings that make climate simulations a controversial, but highly vibrant and, in many ways, astonishingly robust field of research.

Interdisciplinary Explorations of Simulation-Based Knowledge

The Climate Change MECS Conference was therefore an important step toward exploring more fundamentally, in an interdisciplinary framework and often with the help of concrete case studies, the historical, political, and sociocultural dimensions of environmental and climate simulations. Approximately 50 scholars attended from mostly European countries: most scholars were from Denmark, Sweden, France, the United Kingdom, Germany, and Austria, but some from the United States were also present. The conference organizers Isabell Schrickel and Christoph Engemann put together a well-balanced program in many respects, involving almost equal numbers of female and male speakers and commentators while at the same time leaving enough room for early career scholars to discuss their work with senior researchers and university professors.

The conference organizers called for contributions on historical and recent case studies as well as theoretical contributions that question the cultural conditions and effects of a simulation-based order of knowledge. Given MECS' intellectual orientation toward cultural and media analysis, as well as a strong interest in material culture, the organizers again found a refreshingly well-balanced disciplinary distribution, allowing for the highly fruitful confrontation of diverse approaches, ranging from anthropology, art history, and geography to the history of science, science and technology studies, and policy and media analysis, just to name a few. This methodological and disciplinary diversity was of course also reflected in the presentations that ranged from historical case studies to aesthetical reflections and climate policy analysis. And as is often the case during inspiring conferences with interesting participants, the lively discussions continued throughout the breaks, allowing the attendees to discuss themes of great trans-disciplinary potential and to exchange in more depth on various topics as well as disciplinary tools and approaches.

Four thematic panels, accompanied by invited comments, a keynote lecture delivered by Paul Edwards (University of Michigan), and a closing presentation by Oliver Geden (German Institute for International and Security Affairs) made up the general structure of the conference.

The Challenges of Simulation-Based Knowledge

Two principle challenges provide for a transversal reading of the rich and diverse conference contributions: first, the challenges faced by reconciling local needs with the increasingly global perspectives imposed by simulationbased knowledge, and second, the challenges of model and simulation results generated at a science-policy level.

The data, images and global projections that various modeling technologies and simulation processes have produced since the 1970s and 1980s in diverse domains (such as environmental risk evaluation, environmental remote sensing, and climate change research) all feed into a global perspective on the environment that is not easy to reconcile with local needs. Numerous contributions during the conference insisted on a shift away from the human perspective to a more dynamic and mostly statistical approach. Dania Achermann (Aarhus University) explained this is a result in particular of the historical development of the notion of climate that shifted over the 19th and 20th centuries from a stable, timeless, and human object to a dynamic, statistical, and space-related concept. Paul Edwards argued that the steadily increasing complexity of climate models reflects this development as well, where great emphasis is placed on global geophysical processes, often to the detriment of a more local, human perspective. Birgit Schneider explained that this development is also confirmed by most of the scientific images reproduced in the IPCC (Intergovernmental Panel on Climate Change) reports.

Sabine Höhler (KTH Stockholm) provided another excellent case in point: the scientific construction of a global geophysical phenomenon with the help of remote sensing technology, such as the El Niño event, where the transition from rich, local stories to a global, but shallow view of the environment becomes evident. The "grounded" views of century-old oral traditions were gradually supplemented during the second half of the 20th century by increasingly global views. One problematic outcome is that the new global framing and storytelling stripped El Niño of its catastrophic meaning, turning it into a recurring, regular geophysical pattern.

Nonetheless, some of the contributions also pointed at possible solutions for reconciling local perspectives with global modeling. For instance, Sébastien Nobert (University of Leeds) presented a case study on EFAS, a pan-European flood warning system. With EFAS, new networks and democratic ideals were able to emerge. While promoting equal rights to security and well-being throughout Europe, it also placed emphasis on participatory action. EFAS evolved out of EPS, an ensemble prediction system. First introduced to overcome deterministic weather forecasts with an ensemble of predictions that allowed pushing further the time limitations for reliable weather predictions, EPS's success in meteorology led eventually to its application in real-time flood forecasting. By implementing a probabilistic approach in the forecasting process and by making uncertainties more explicit, it favored the establishment of a flexible distribution of authority, permitting different actors to take decisions at different level. Yet this new framework did not just redistribute power, it also required a new form of training for scientists, new organizational constellations, and a fragmentation of the social in order to prioritize individual response over collective reaction.

Other contributions, such as Paul Edwards' keynote address, resonated with Nobert's suggestions. For instance, in climate modeling, recent initiatives place a strong emphasis not on further scaling-up objectives but rather on interoperability processes and common methodologies in order to transform useful knowledge into usable knowledge. For Edwards, this is a question of knowledge infrastructures. By sharing all kinds of data via open-knowledge databases, by mobilizing existing resources that are already at our disposal, and by shifting to a more integrative, but also more pragmatic problem-solving approach in science, we may indeed serve more local needs and allow for a better, more usable knowledge production that can help tackle the serious and diverse problems we face within climate change.

Carson Chan (Princeton University) added to this view a social dimension, proposing to update Anderson's concept of "imagined communities" by taking into account new social spaces such as "Diaspora space," where migrant groups and NGOs (nongovernment organizations) also have a voice. According to Chan, the so-called digital revolution, with its self-fulfilling myth of free access to information, helped create new communities within cyberspace where ideas have become more important than geography. Here, however, a more critical approach to the digital revolution, beyond the well-known homage to freedom of speech and democratic ideals, especially concerning some of its problematic political and economic effects, would have been welcome.

A second crosscutting challenge was how simulation-based knowledge relates to and interacts with the political sphere. Especially within climate change research, the science-policy interface is an intensely discussed topic. As geographer Martin Mahony (King's College, London) pointed out, the evolution of climate modeling in the UK was influenced by strong political interactions with the scientific community. Indeed, politics and science mutually constructed the practices, norms, and priorities of climate science in the UK. The turn to transient climate simulations was for example initiated under Margaret Thatcher and global climate modeling emerged mainly from the political aim of internationalism and the struggle for UK leadership in Europe.

Many other speakers picked up this topic of political and scientific co-construction, such as art historian Birgit Schneider (Potsdam University), who pointed at the normative function of climate imagery. She showed how the IPCC explores and tests future visions with the help of graphs, maps, plots, and charts and more importantly how the IPPC makes normative statements about which future visions are preferable (the colors red and blue for example have precisely this function). In doing so, Schneider made the important point that climate images have agency: by shaping our imagination, they necessarily change reality. Schneider feels that climate modelers especially should be made more aware of this point and other speakers, such as Alexander Bakker (Pennsylvania State University), complemented her argument by pointing at social norms that also play an important role within climate modeling (such as "implicit tuning," where successful parameterizations are shared among modelers). And just as climate images contain normative elements, clearly indicating preferable climate visions, Samuel Randalls (University College London) discussed how other cultural artifacts such as climate online games also can come to legitimize certain economic ideals and make them seem more respectable than others.

Finally, calling on the responsibility of climate modelers and policy makers alike, Olivier Geden (SWP German Institute for International and Security Affairs) concluded the conference on a rather critical, if not alarming note. Drawing on research conducted on the science-policy interface in recent climate change discussions on geoengineering technologies, Geden argued that we are dramatically shifting from "evidencebased policy making" to "policy-based evidence making." His example of a completely untested and highly risky technology known as BECCS (bio-energy with carbon capture and storage) allowed him to make an important point: today, policy makers deliberately ignore the uncertainties of the scientific studies to legitimize their inactions; the modelers, on the other hand, even though they don't believe that their scenarios are realistic, because they know about the inherent uncertainties, are not sufficiently aware of their part of responsibility in the coproduction of this irresponsibility. Although critical public discussion might finally bring down BECCS, other forms of geoengineering are likely to enter the modeling process in the near future, such as solar radiation management (SRM). This dangerous development can only be prevented by profoundly reshaping the sciencepolicy interface.

Conclusion

Simulation-based knowledge proved to be a highly productive topic at the "Dealing with Climate Change" conference. The participants' willingness to go beyond the usual epistemological discussions proved especially fruitful, deepening and enriching our understanding of climate models and environmental simulations. Indeed, the diverse and rich contributions and discussions showed not only how simulation-based knowledge profoundly changed the way we perceive and conceptualize climate change and environmental risk in general, but also how cultural and social norms, policy aims, and economic ideologies intervene in this complex historical process.

Finally, and maybe most importantly, the compact two days provided for some engaging and lively discussions between researchers of various disciplinary backgrounds, often continued outside of formal sessions, allowing for new social ties to be established that will certainly show their fruits in the near future.

Sebastian Grevsmühl is a postdoctoral research at Pierre and Marie Curie University (Paris 6) in the History of Nuclear Energy and Society (HoNEST) research group. Contact him at sebastian.grevsmuhl@upmc.fr.

This Events & Sightings installment covers a range of recent events focusing on the history of computing. history of computing, computer simulations, climate simulations, climate research, climate models


Shlomo Barak
email: shlomo@tagapro.com

Time is not Fundamentalunlike Distance and Velocity

Keywords: Time, Distance, Light velocity, General relativity, Special relativity

Distance and time are considered fundamental attributes of the reality and the result of their division is velocity. In this paper we suggest, in contrast, to consider distance and velocity as fundamental and time as merely a practicality. This approach yields a new understanding of physics.

We can build devices called clocks; whose hand movement (or whatever is analogous to the hand movement) describes to us the "passing of time". The time of an event would be the position of the hands at the moment, and at the place of the event. The hands of the clock must move in a rhythmic circular motion so that each cycle is exact. In the case of a noncircular, but rhythmic motion the physical conditions must be preserved so that every motion is like the one preceding it. Thus we can talk about the clock's rhythm, or frequency of its motions, where each cycle represents a unit of time.

Note that all the equations in physics are invariant to time reversal.

Distance 1.2

In a space lattice [START_REF] Barak | The Geometrodynamics of Space[END_REF] the distance between two points is simply the number of space cells on the straight line between the two points for a Euclidian space and on the geodesic for a Riemannian (deformed) space.

On Two Fundamental Velocities 1.3

The Greek philosopher Zeno contended that there is no motion. In contrast, in our theorythe GDM [START_REF] Barak | The Geometrodynamics of Space[END_REF], there is no rest, see Section 4.1(this paper), and only two fundamental velocities exist.

The GDM considers the space lattice to be elastic with only two real fundamental velocities; that of transversal waves, and that of longitudinal waves. Transversal waves are shown to be the EM waves [START_REF] Barak | The Geometrodynamics of Space[END_REF], [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF] (and references there). Longitudinal waves are shown to be related to the inner motion in elementary particles (not discussed here) [START_REF] Barak | The Geometrodynamics of Space[END_REF], [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF]. The Navier equation governs elastic media. Its solution for elastic transversal waves gives the expression for light velocity [START_REF] Barak | The Geometrodynamics of Space[END_REF]:

c' = √(μ/m ) (1)
where μ is a Lamé coefficient and m is the mass density of the media. Since space is massless we take m as:

m = ϵ s /c 2 (2)
where ϵ s is the standard space energy density, and c is the relevant light velocity. Inserting [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF] into (1) gives:

c' = c√(μ/ϵ s ) (3)
Thus [μ] = [ϵ s ], and we can rename the numerator and use ϵ instead of μ. Thus (3) becomes:

c' = c√(ϵ/ϵ s ) (4)
By using (2) we have turned [START_REF] Barak | The Geometrodynamics of Space[END_REF], an equation that determines c', into an equation ( 4) that determines the ratio c'/c. But light velocity is determined by the permittivity and permeability of space and hence by the tension in the space cells. This tension is dependent on the energy per cell; hence the relation:

ϵ/ϵ s = ρ 0 /ρ ( 5
)
where ρ is space density and ρ 0 is the standard space density -no deformations. Substituting (5) in (4) gives:

c' = c√(ρ 0 /ρ ) (6)
Every space disturbance, a transversal or longitudinal wavepacket, must move at the velocity c T or c L, respectively. We distinguish between c T and c L when necessary. In most cases we use the symbol c instead of c T.

The Cosmic Microwave Background (CMB) 2

At large, the CMB is isotropic and homogenous blackbody radiation, with a peak temperature of 2.7k. The CMB was predicted theoretically by Gamow and discovered accidentally by Penzias and Wilson [START_REF] Penzias | [END_REF]. In 1989 the CMB was again measured, this time by the Cosmic Background Explorer (COBE) satellite [5], see Fig. [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF]. An observer's motion relative to the background radiation is accompanied by a Doppler shift. This shift enables the measurement of the observer's velocity relative to the radiation bath "attached" (i.e., space's vibrations) to space.

Velocity Relative to Space 3

A CMB anisotropy was first observed by Smoot et al [START_REF] Smoot | Wrinkles in Time[END_REF], and interpreted as the result of the above Doppler shift [START_REF] Rowan-Robinson | Ripples In The Cosmos[END_REF]. Fig. [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF] shows the vector of the velocity of planet Earth relative to the universe [START_REF] Muller | The Cosmic Background Radiation and the New Aether Drift[END_REF]. Recently, the velocity of the Earth around the Sun and its rotational velocity have been derived from the Doppler shift.

Earth's velocity relative to space is: v = 371.0 ±0.5 km sec -1 . This velocity is towards a point with equatorial coordinates: (α,δ) = (11.20 h ±0.01 h , -7.22 0 ±0.08 0 ), [9]. This direction points from the cluster of galaxies, Aquarius, towards the cluster Leo-Virgo.

Say the peak of the background radiation is green. An observer, seeing green in all directions, knows they are at rest relative to space. An observer, seeing blue in one direction, red in the opposite direction, and green on the sides, knows they are moving in the direction of the blue.

Similarly, we can also make a distinction regarding acceleration.

An observer moving in a circle notices that, tangentially to the circle, there is no symmetry; the horizon in one direction looks red, and in the other, blue. Coleman and Glashow [10], [11], also adopted this idea that space is a special frame.

The CMB necessarily "resides" in the same "stationary system", which is the space lattice.

Note that for observers on Earth, with velocity v relative to the space frame, v << c, and γ ~ 1+1/2•v 2 /c 2 ~ 1+ 3•10 -7 . Thus, ignoring 3•10 -7 and taking γ = 1, we are left with the SR notion that only relative velocity matters, as if there is no special frame.

Rest and Motion and Length Contraction 4 "Rest" 4.1

In the GDM "rest" is related to the situation in which a wavepacket moves in a closed loop. In this case the geometrical center of the circulating wavepacket is at rest. The particle, which is this wavepacket, can be regarded as staying at "rest".

The electron (positron) at rest is a circulating longitudinal dilational (contractional)

wavepacket with a tangential velocity of propagation c and radius of circulation R 0 . In [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF] we elaborate on this circulation which is actually more complex. Thus, from a distance, the electron (positron) is observed as if at rest, and from close, as a volumetric dilation (contraction), which is its negative (positive) charge that moves in a circle [START_REF] Barak | On the Essence of Gravitation and Inertia, Part 1: Inertia and Free Fall of an Elementary Particle[END_REF] . 1) is a simplistic description of the electron (positron). The gray sphere (circle) represents the zone of dilated (contracted) space, which is the electric charge. In this discussion we omit, for simplicity, the circulation of the charge, with radius r e around its surface, as shown in the detailed model in [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF]. We also do not show in Fig. [START_REF] Barak | The Geometrodynamics of Space[END_REF] that the circulation plane is not perpendicular to the velocity vector v. The projection of the angular momentum L, of this circulation, on v is L z = 1/2 ℏ whereas L = ℏ√j(j + 1) = ℏ√1/2(1/2 + 1) = 0.866 ℏ , hence the inclination of the circulation plane. "Rest" is described on the left of Fig. [START_REF] Barak | The Geometrodynamics of Space[END_REF]. The zone of dilated space (charge) of our electron revolves, in the xy plane, around the origin with a radius R 0 . In this case: c = R o . From now on, when we relate to the electron we also relate to the positron, unless otherwise mentioned.

The electron model, presented here, is a simplified version of a much more detailed model that appears in [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF] and yields accurately the leptons' masses and some other features. 1), on the right, describes motion. Motion is the situation in which the circle of revolution of a wavepacket becomes a spiral. The GDM considers the length of the wavepacket to be retained. From this conjecture alone we derive the results of the Theory of Special Relativity (SR). Since the length of the wavepacket is retained, the spiral radius R is smaller than R 0 . This is analogous to a stretched spring. As Fig. [START_REF] Barak | The Geometrodynamics of Space[END_REF] shows:

R = 1/  R 0 Microscopic Contraction (7)
The resultant electron motion is always at the wave velocity c. Thus a translatory motion at constant velocity, v, does not involve any exertion of force and necessarily v  c.

z x y v c C1 2 2 2 1 v c c   or:   c γ 1 β 1 c c 2 1 2 1   
where: c v β  and:

  2 1 2 1      c Motion "Rest"

Fig. (1) Rest and Motion

Newton's first law, and the first postulate of the theory of relativity, which implies that no particle or signal can move at a speed that exceeds the light/wave velocity c, are thus a natural result. The helical motion, which is an electric current formally in the direction -z, is related to the magnetic field B and the vector potential A. The Circular Track is stable since the centrifugal force is balanced by an equal but opposite centripetal force. The Lorentz force, created by the magnetic field of the circulating charge acting on itself, is the required centripetal force, see [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF].

The Elementary Particle Inertia and Length Contraction 4.3

At rest, the energy of the electron is U 0 , linear momentum is P o = U 0 /c and the angular momentum is L 0 = P o R o .

In motion, energy, linear momentum and angular momentum are U, P = U/c and L = PR respectively.

The conservation of angular momentum L = L 0 (which is 1/2  for the electron) implies that: [START_REF] Rowan-Robinson | Ripples In The Cosmos[END_REF], thus:

PR = P o R o . Hence UR = U 0 R 0 , but R = 1/  •R 0 ,
U = γU 0 ( 8
)
Considering the energy as purely electromagnetic, where the elementary charge Q is a sphere of radius r 0 [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF], the relations U 0 = Q 2 /2r 0 , U= Q 2 /2r and (2) give:

r = 1/  • r 0 Microscopic Contraction (9)
For v << c ( 9) is: r = (1-v 2 /2c 2 ) r 0 (10) Acceleration is accompanied by an increase of energy U, and a reduction in the radii R and r.

The applied force, needed to accelerate the particle, is doing work to curve space more strongly and thus to reduce r. This force is needed to increase stress and cause more strain in order to enlarge the curvature. Thus we arrive at Newton's Second Law and understand

where Inertia comes from.

Note that we have replaced Newton's axiomatic laws by our postulated model of an elementary particle. Some of the merits in this replacement, as we show, are:

 It leads to the proof of the equivalence of gravitational mass and inertial mass [START_REF] Barak | On the Essence of Gravitation and Inertia, Part 1: Inertia and Free Fall of an Elementary Particle[END_REF].

 It proves that mass is not a fundamental attribute of matter (Section 4.4).

 It proves that inertia is an intrinsic attribute of matter, with no need for an additional field to induce it (Higgs Field).

Note that the relations L= 1/2  , R=1/2  c/ U, U 0 = Q 2 /2r 0 and r = Q 2 /2U give:

α = r/R = Q 2 /  c Fine Structure Constant. (11)
Note also that at "rest" the angular momentum can point in any direction, whereas in motion it can point, generally (see Section 3.1), in the direction of motion or opposite to it. This attribute is related to Space Quantization.

Mass 4.4

Our "relativistic" relation (2) gives:

2 2 0 0 2 1 2 2 0 0 c v U U c v 1 U γU U 2 1               The second term: 2 2 0 c v U 2 1 = ½(U 0 /c 2 )v 2 ,
is identified as the kinetic energy where:

M 0 = 0 U / c 2 (12)
Thus inertial mass becomes merely a practical term. We also get: M = γM 0 [START_REF] Purcell | [END_REF] The literature distinguishes between the kinetic energy ½ 2 0 v M , which a particle possesses by virtue of its motion, and its internal energy 2 0 c M . But here, the kinetic energy is also an internal energy of deformation (the reduction in size of r and R) that cannot be distinguished from the rest energy.

Note again that the electron model, presented here, is a simplified version of a much more detailed model that appears in [START_REF] Barak | On the Essence of Electric Charge Part 2: How Charge Curves Space[END_REF] and yields the masses of the leptons and quarks.

The Contraction of Macroscopic Bodies 5

Fitzgerald and Lorentz (1904) explained the then lack of ability to discover motion relative to the aether (Michelson and Morley 1887) assuming that the lengths of bodies are contracted in the direction of their motion:

0 2 1 2 2 0 L 1 c v 1 L L             Lorentz Length Contraction (14)
The translational velocity v is with respect to space, as we see it. An observer moving in space would not notice any contraction, since not only the yardstick but also they are contracted. However, they can always measure their velocity relative to space and calculate their own contraction. At this stage we can only speculate as to why and how a macroscopic body in motion is contracted.

We consider a possible explanation for macroscopic contraction.

According to Bell [START_REF] Bell | Speakable and Unspeakable in Quantum Mechanics[END_REF] pp. 69-78, and our exploration [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF], the electric field of a moving charge is:

  2 3 2 2 2 2 ' sin 1 1 r' HQ E'       (15)
We denote the distance from the charge Q, momentarily at the origin, to the point (x',z')

where the field is measured:

  2 1 2 2 z' x' r'  
. ' denotes the angle between this radius vector and the velocity of the charge Q, which is moving in the positive x' direction in the frame k'.

Then, since z' = r' sin ', [START_REF] Barak | On Curved Manifolds and Deformed Spaces hal-01498435[END_REF] is the magnitude of the field.

For low speeds the field reduces simply to E'  HQ/r' 2 . But if  2 is not negligible, at the same distance from the charge, the field is stronger at right angles to the motion than in the direction of the motion. Fig. [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF] shows a simple representation of the field indicating field lines in the x'z' plane. For the field in the x'y' plane we get an identical representation.

Fig. [START_REF] Barak | Electromagnetism as the Geometrodynamics of Space[END_REF] shows that the field perpendicular to the direction of motion gets stronger whereas in the direction of motion -weaker. This phenomenon [START_REF] Bell | Speakable and Unspeakable in Quantum Mechanics[END_REF] explains macroscopic contraction, since the orbits of electrons in atoms are distorted to become ellipses with their shorter axis in the direction of motion.

Fig. (2) Representation of the Field of a Uniformly Moving Charge

Light Deflection 6

Fig. (3) shows a projector consisting of a point radiator located at 0, the focal point of a parabolic mirror. When the projector does not move, v = 0, the radiation reaches both edges of the reflector at the same time, and the outgoing beam from the reflector moves toward the ceiling with its wave front parallel to the ceiling. When the projector is on the move, v  0, the radiation from 0 reaches the left side of the parabolic mirror before it reaches the right side, thus tilting the wave front and deflecting the beam.

v c t v c t R L     l l 2 2 γ c v 2 t t Δt L R l         Sin t g rad for small           2l c c 2lv 2l c Δt Sin 2 2 0 (16) v A D C B v = 0 v L R o  o l 0 l 0 Fig. (3) A Projector
For an observer moving with the radiator, the beam of light appears as if it is moving perpendicularly to the direction of motion.

Note that the same phenomenon takes place, on a microscopic level, in Synchrotron Radiation.

Larmor Time Dilation 7

The Cell 7.1 4) shows the source S and detector D on the "floor", and the mirror on the "ceiling". If the cell moves in a direction perpendicular to the direction of the beam of light, the observer resting in space sees a deflected beam:

Fig. (4) A Moving Cell 2 2 2 2 T v L 2 T c                 L = L0 ,
since there is no contraction in the direction perpendicular to the direction of motion.

Hence:

  2 2 2 2 0 T v c L 4    and 2 1 2 2 0 c v 1 1 c L 2 T            or 0 T T     Larmor Time Dilation (18)
A Moving Cell with a Beam Parallel to its Motion 7.3 Fig. (5) shows the source S and detector D on one side, and the mirror on the other side.

When the cell and the light beam move at speed v relative to space:

Based on ( 17) and ( 19) we conclude time to be a scalar.

Conclusion 7.4

We consider both length contraction, and light deflection to be real. Thus we have dispelled the need to relate to time as a fundamental attribute of reality. Time appears as simply the division of Distance by Velocity. By virtue of motion, or deformed space, objects and light velocity change in a way that keeps light velocity constant, hence the term constant of nature [START_REF] Barak | On the Essence of Gravitation and Inertia, Part 1: Inertia and Free Fall of an Elementary Particle[END_REF], but time by itself has no meaning. This conclusion has implications as to how we relate to the first term in the Schwarzschild metric:

  . Some physicists wrongly consider c to be constant whereas it is time that changes. We, in contrast, consider c to be a variable, but a constant of nature [START_REF] Barak | On the Essence of Gravitation and Inertia, Part 1: Inertia and Free Fall of an Elementary Particle[END_REF].

Note that a mass contracts space around it (the GDM interpretation of curving [START_REF] Barak | On Curved Manifolds and Deformed Spaces hal-01498435[END_REF]), hence according to Section 1.3 light velocity c, at the mass, is slower than that in inter-galactic space. Space is contracted, but so are the local observer close to the mass and his yardstick.

As [START_REF] Barak | On the Essence of Gravitation and Inertia, Part 1: Inertia and Free Fall of an Elementary Particle[END_REF] shows, the value for c, measured by the local observer, is the same as for the far-away observer. This is the reason for considering c a constant of nature, despite being a variable.

GDM versus Special Relativity (SR) 8

In SR, length contraction and time dilation are not real. In SR, neither space nor time is objective. Only spacetime is objective and absolute, since the interval S 2 is invariant under Lorentz Transformation.

In the GDM, physical objects get shorter in the direction of motion relative to space. Hence, the spatial distance between two disconnected objects, moving in the same direction and at the same velocity, is retained.

SR considers these two objects to reside in the same inertial frame. Thus, an observer in another inertial frame concludes that not only the objects get shorter, but also the spatial distance between them.

Case Study 9

Consider two rockets, at rest, a distance L 0 from each other. The rockets start to move till they both acquire velocity v, relative to the space frame k. We assume a very slow and identical acceleration for both rockets until they reach this velocity.

In Fig. [START_REF] Smoot | Wrinkles in Time[END_REF] a beam of light travels from a source S, on the left rocket, to a mirror M, on the right rocket, and back to a detector D. Since L = L 0 for an observer at rest in the space frame k, the time taken to travel according to the GDM is:

T c v 1 1 c L 2 v c L v c L T           (19)
where ∆T 0 = 2L 0 /c . This difference, between (19) and (18), is the difference between the predictions of the GDM and SR.

On the Lifetime of the Muon 10 SR Interpretation 10.1

The muon particle decays via the weak interaction into an electron and a pair of neutrinos after 2.2 microseconds. In the late 1990s, scientists at Brookhaven National Laboratory, used the Alternative Gradient Synchrotron (AGS) to produce a beam of muons circulating around a 14m-diameter ring at a speed of 0.9994•c. Muons lifetime, at rest, is 2.2 microseconds. If this is also the lifetime at this speed, they would manage no more than 15 turns of the ring before they disintegrate.

But the muons managed around 433 turns, which means their lifetime was extended by a factor of 28.8 to just over 60 microseconds.

And indeed, for a speed of 0.9994•c the Lorentz factor of time-dilation is: γ = 28.87.

SR predicts, as observed, that these speedy muons should live 28.87 times longer than at rest.

According to SR, we can also argue that space in the frame of the muon, which moves with a tangential velocity 0.9994•c relative the Lab frame, is contracted, Lorentz contraction, by the same γ = 28.87. And as a result the muon, with its lifetime of 2.2 microseconds, moves 433 times around this contracted circumference. The fact that there are two alternate SR explanations is confusing.

GDM Interpretation 10.2

Our model, Section 4.1 Fig. [START_REF] Barak | The Geometrodynamics of Space[END_REF], of the elementary particle, and equations ( 7) and (9), show that when it moves it gets smaller: R =1/γ R 0 , r = 1/γ r 0 . Fig. [START_REF] Rowan-Robinson | Ripples In The Cosmos[END_REF] shows that the muon disintegrates via its interaction with the vibrating space around it. Hence the smaller it becomes the weaker is the interaction. The interaction dependence on γ is, therefore, reflected in the dependence of the particle's life time on γ: τ = γ τ 0

  We do not know what time is, we only know what motion is.

  Fig. (2) The Cosmic Background

Fig. ( 3 )

 3 Fig. (3) Earth Velocity Relative to the Space

Fig. (

  Fig. (1) is a simplistic description of the electron (positron). The gray sphere (circle)

Motion 4. 2 Fig. (

 2 Fig. (1), on the right, describes motion. Motion is the situation in which the circle of

Fig. ( 4 )

 4 Fig. (4) and Fig. (5) show a cell with sides L 0 . The cell is equipped with a source S and

  Fig. (5) A Moving Cell

Fig

  Fig. (6) Two Rockets

For the observer on

  the left rocket ΔT = γΔT 0 , since the unit of time of his clock is dilated.In SR the two rockets reside in the same reference frame k', hence relative to k is contracted and the travel time is: ΔT = γΔT 0 , equation (18).

Fig. ( 7 )

 7 Fig. (7) Feynman Diagram of the Muon Decay

Acknowledgements

We would like to thank Mr. Roger M. Kaye for his linguistic contribution and technical assistance.

Summary 11

Real motion is only that of the transvers or longitudinal waves. Space is a special frame and motion relative to space causes real contraction and deflection. These phenomena dispel the need for relating to time as fundamental attribute of reality. The saying that "Time is Money", albeit with a different connotation, expresses our understanding that Time is indeed like Money.


Nicolas Candau

Jean-Luc Bouvard

Edith Peuvrel-Disdier

Rudy Valette

Noëlle Billon

Effect of stretching on the network structure of carbon black filled EPDM rubbers

Keywords: EPDM, volume measurement, thermoporosimetry, rubber network damage

  L'archive ouverte pluridisciplinaire

Introduction

Carbon black filled ethylene-propylene-diene-monomer (EPDM) has been widely studied in the recent years. Thanks to its good electrical properties, high resistance to ageing and mechanical properties, it is one of the best candidates for the automotive industry. The improvement of its mechanical properties should be based on a good understanding of the microstructural changes induced by loading. The damage mechanisms, i.e. cavitation / decohesion, are usually studied in the literature by in-situ SAXS [1] or volume changes [2]. However, to the authors' knowledge, no study was devoted to microstructural characterization allowing taking into account the heterogeneity of the rubber network. Thus, the present work proposes an approach to identify the network structural evolution of EPDM rubbers induced by loading combining volume measurements, swelling and thermoporosimetry.

Materials and experiments

The materials of the study are an extended and a non-extended oil carbon black filled EPDM obtained by sulphur vulcanization of the gum. They contain 80phr of carbon black (80 g of fillers per 100 g of rubber). The extended rubber contains 65 phr of paraffin oil.

EPDM samples were stretched uniaxially at room temperature with the strain rate 10 -1 s -1 up to various stretching ratios λ. Tests were performed on an INSTRON tensile test machine. Two camera pairs -allowing neglecting the out of plane displacements -were positioned to measure the strain displacement field on the front and side faces of the samples. A speckle pattern was put on the surface sample. Digital Image Correlation was then used to measure the evolution of the displacement field during the mechanical test, giving access to the relative volume variation during loading ∆V/V. Tested samples were then stored at 21°C during one week to allow slow reversible reorganization of the polymer chains. The center of the sample was then cut and submitted to post-mortem characterization. The effective network chain density (ν) -containing filler/rubber bonds, trapped entanglements and chemical crosslinksis estimated from swelling in cyclohexane, from the Flory-Rehner equation [3] and the Kraus formula [4]. Swollen samples were then put in a DSC to perform thermoporosimetry experiments [5] in order to have access to the pores size of solvent confined in the polymer network (cooling from 21°C to -50°C at 10°C/min, holding at -50°C during 2min and heating at 10°C.min -1 up to 30°C). During heating, the first peaks that appear correspond to the melting of the cyclohexane entrapped in the network. The last peak corresponds to the melting point of free cyclohexane T s =7°C (i.e. in excess), corresponding to infinite crystal.

Results and discussion

EPDM rubbers were stretched at 10 -1 s -1 and at 21°C up to λ=4. The loading is associated with an increase of volume (∆V/V) up to 2% and 3.5% for extended and non-extended rubbers respectively. The higher ∆V/V value for the non-extended rubber compared to extended one is likely due to the higher stress experienced during stretching (because of higher volume fraction of fillers) which thus eases cavitation/decohesion. As compared to virgin samples (not submitted to loading), the effective network density of tested materials (ν) is decreased of 7% and 8% for extended and non-extended EPDM respectively. These results confirm that irreversible modifications take place in the network structure during stretching. Besides, a slight increase of the sol fraction of the tested rubber samples compared to virgin ones suggests that part of the chains are excluded from the elastically active network chains.

To further analyze the microstructural changes, thermoporosimetry experiments were carried out on the oil extended EPDM. Virgin and tested samples exhibit two principal melting peaks T 1 and T 2 below the melting peak of free solvent T s ; suggesting the existence of two chain length populations. T 1 and T 2 are found higher in tested samples compared to those of the virgin ones. Then, the higher is the melting temperature; the larger is the average chain length (i.e. the lower is the effective network density). As a result, damage during stretching is accompanied by an average increase of all chain length populations.

These changes should be significantly increased for samples stretched up to the rupture (λ=8). Indeed, in that case, the effective network density is decreased of more than 20%. These results as well as complementary loading conditions (stop at various λ, accumulation of cycles at given λ) will be presented during the conference.

Conclusion

This work presents a new experimental approach for the study of the damage mechanisms in rubbers. An experimental device based on two camera pair systems has been developed in order to accurately measure the volume change of rubber samples during stretching. Post mortem analysis of the microstructure, combining swelling and thermoporosimetry experiments, were carried out. A good agreement has been found between the volume change and the microstructural evolution. They show a progressive damage of the rubber during stretching. By analyzing more complex loading conditions, this methodology should be an interesting way to more precisely identify irreversible mechanisms induced by stretching.

Acknowledgements

The authors are indebted to the company SACRED for providing and processing of the rubber gum and to the laboratory GEPEA of the University of Nantes for the detailed set up of the curing procedure of rubber materials. This work was performed in the framework of the project ECOTHER supported by BPiFrance.