Claire Dalmay

M A De Menorval

Olivier Français

L M Mir

B Le Pioufle

A microfluidic device with removable packaging for the real time visualisation of intracellular effects of nanosecond electrical pulses on adherent cells

come

A microfluidic device with removable packaging for the real time visualisation of intracellular effects of nanosecond electrical pulses on adherent cells

I. Introduction

Cell electropermeabilization is a well-known technique that requires a short duration and an intense electric field to destabilize the plasma membrane. This technique is now mature and used in the field of cancer therapies in order to enhance the efficiency of targeted delivery of materials like drugs, antibodies or genes [START_REF] Domenge | Antitumor electrochemotherapy: New advances in the clinical protocol[END_REF][START_REF] Marty | Electrochemotherapy -An easy, highly effective and safe treatment of cutaneous and subcutaneous metastases: Results of ESOPE (European Standard Operating Procedures of Electrochemotherapy) study[END_REF][START_REF] Mir | High efficiency gene transfer into skeletal muscle mediated by electric pulses[END_REF].

Electropermeabilization results from an interaction between the applied electric field and the cell plasma membrane, which increases its permeability. For a circulating cell (assumed to be spherical) the transmembrane potential Ψm is time dependent, following the charging of the plasma membrane (1) [START_REF] Schwan | Electrical properties of tissue and cell suspensions[END_REF][START_REF] Kotnik | Analytical description of transmembrane voltage induced by electric fields on spheroidal cells[END_REF].

! m = f .E.R.cos(! ).[1" e " t " m ] (1)
where R represents the cell radius, f is function of the cell geometry, θ stands for the angle between the electric field E and the cell radius vector. The time constant τm, characterizes the dynamics of the charge of the membrane [START_REF] Kotnik | Analytical description of transmembrane voltage induced by electric fields on spheroidal cells[END_REF]. The case of adherent cells is more complex, and some simulation study on cell tissues can be found in [START_REF] Miklavcic | The importance of electric field distribution for effective in vivo electroporation of tissues[END_REF].

In the case where conventional electropermeabilization pulses are applied (such pulses having few 100 µs duration), the transmembrane potential reaches ! m = f .E.R.cos(! ) , once t>>τm " order of µ sec . In this case, the cell membrane shields the electrical field that does not penetrate inside the cell, as long as the membrane is not permeabilised [START_REF] Kotnik | Theoretical Evaluation of Voltage Inducement on Internal Membranes of Biological Cells Exposed to Electric Fields[END_REF][START_REF] Gowrishankar | Intracellular electroporation site distributions: Modeling examples for nsPEF and IRE pulse waveforms[END_REF].

With the recent technical progresses in the field of pulsed power equipment, the use of ultra short duration pulses (typically 3 to 10 ns) and high intensity (up to 100 kV/cm), also called nanosecond pulsed electric fields (nsPEF) has been investigated. The nsPEFs, implying a high frequency electric field spectrum (from DC and above 100MHz), are able to penetrate inside the cells, as the plasma membrane is shortcircuited at these working frequencies (t<<τm). Hence, nsPEFs are able to disturb the membrane of intracellular organelles as internal vesicles, mitochondria [START_REF] Napotnik | Nanosecond electric pulses cause mitochondrial membrane permeabilization in Jurkat cells[END_REF] or endoplasmic reticulum [START_REF] Vernier | Calcium bursts induced by nanosecond electric pulses[END_REF][START_REF] Craviso | Nanosecond electric pulses: a novel stimulus for triggering Ca2+ influx into chromaffin cells via voltage-gated Ca2+ channels[END_REF]. Nevertheless, we are at the beginning of this very exciting area of manipulating cell interior whose mechanisms remain still misunderstood.

In this context, researchers need tools allowing the real time visualization of cell perturbations induced by the application of nsPEFs. In particular, the microtechnologies offer high miniaturization capabilities allowing the generation of highly intense nanosecond electric fields, suitable to penetrate the intra-cytoplasmic compartment. Moreover, the use of transparent material to microfabricate such miniaturized devices allows real time imaging of the effects of such nanopulses.

Especially, the nanoporation of adherent cells requires a particular attention, as these cells need to be cultured and attached on a substrate to be in proper conditions mimicking usual cell environment, prior to nPEFs exposure. While many studies exist in the literature concerning the electropermeabilization of circulating cells on a chip [START_REF] Huang | Microfabricated electroporation chip for single cell membrane permeabilization[END_REF][START_REF] Lin | Electroporation microchips for continuous gene transfection[END_REF][START_REF] Le Pioufle | Living cells captured on a bio-microsystem devoted to DNA injection[END_REF][START_REF] Lee | Microscale electroporation: challenges and perspectives for clinical applications[END_REF][START_REF] Wang | Cardiac Myocyte Excitation by Ultrashort High-Field Pulses[END_REF], including our work [START_REF] Dalmay | A microfluidic biochip for the nanoporation of living cells[END_REF], very few developments of micromachined devices adapted to the electrical treatment of adherent cells can be found. Hence, we propose in this paper an original approach where adherent cells cultures, prepared ex-situ on conventional glass slides, can be reported on our microfluidic device, thanks to a specific design. With this approach, one given microdevice can be re-used and easily cleaned for many experiments, where cells are cultured on glass slides prepared separately in large numbers. This concept of removable packaging is here advantageously exploited for adherent cells exposure to nsPEFs and for the real time monitoring of the effects of the nsPEFs, focusing on the generation of internal calcium concentration peaks resulting of membranes nanoporation.

II. Materials and Methods

A. Microfluidic biochip design

In this section we describe the design of the new microfluidic device (Fig. 1(a)) that was specifically developed for the observation and study of the effects of nsPEFs on adherent cells. Impedance matching aspects:

Due to the high voltages (up to 10 kV) applied to obtain the high field amplitude of the nsPEFs, the impedance matching with the nanopulser is crucial in order to prevent any damages of the electronic components. Indeed, the level of reflections of the transmitted energy back to the nanopulser depends on this matching, which in addition affects directly the transfer of energy to the cells [18,-20].

As the electric field is applied to the biological medium with thick electroplated gold electrodes, the impedance is mainly governed by the physical properties of this medium. The propagation along the electrodes can be neglected for the considered frequency spectrum of the nsPEFs which energy is mainly located in the range (0-100 MHz), when 10 ns duration pulses are considered [18,-20]. The medium is mainly conductive at low frequencies (for f << " 2.# .$

) and capacitive for higher frequencies,

where " and " are respectively the conductivity and permittivity of the medium.

The impedance matching cannot be achieved for all frequencies but can be optimized in a large frequency bandwidth, where the medium is considered as a pure conductance, and which includes the main energy frequency range of the nanopulses.

To do so, the geometrical parameters of the device (thickness t of the electroplated electrodes, the distance d between these electrodes, the length L and height H of the micro channel) are adjusted to get the required 50 Ω impedance for the [0 to 200 MHz] frequency bandwidth, suitable with the delivery of 10 ns nanopulses with the available nanopulser generator described later, in the experimental section [START_REF] Dalmay | A microfluidic biochip for the nanoporation of living cells[END_REF][START_REF] Dalmay | Design and realization of a microfluidic device devoted to the application of ultra-short pulses of electrical field to living cells[END_REF][START_REF] Silve | Nanosecond-duration electric pulse delivery in vitro and in vivo: experimental considerations[END_REF][START_REF] Silve | Nanosecond pulsed electric field delivery to biological samples : difficulties and potential solutions[END_REF][START_REF] Silve | Demonstration of cell permeabilization to medium-sized molecules caused by a single 10ns electric pulse[END_REF]. While d and t are respectively set to d=150 μm and t=25 μm, L and H depend on the chosen architecture (see next section). Removable packaging architecture: For adherent cells to be exposed to the nsPEFs solicitations, it is mandatory to let the cells incubate and adhere on the substrate prior to field exposure. An at least 4 hours incubation in sterile conditions, at 37°C -5 % CO2, is required. A cell culture directly performed within the microfluidic device is quite achievable but leads to several constraints i) only one or two exposures per day are possible, as 4 h are required for the adhesion and spreading of the cells, ii) a specific cleaning of the device is necessary after each experiment. The lifetime of the device is thus decreased, due to this needed cleaning procedure.

In order to avoid the drawbacks mentioned above, we developed a specific packaging, well adapted to our case where adherent cells are exposed to nsPEFs within the microfluidic device. The solution that we propose involves the possibility to use removable coverslip. Indeed this strategy presents the advantage to allow the culture on several cover slides in parallel while the biochip is available for short term (or even very short term) experimentations. The cleaning of the biochip is highly facilitated as the cell adhesion is not promoted within the channel surfaces. Thus, the device lifetime is increased.

The structure that we developed is represented on Figure 1.(b). Two different configurations have been investigated, each of them including an external frame in thick resist (SU8, Microchem) that allows the positioning of the 12 mmx32 mm culture cover slides above the metallic electrodes. Notches have been included in the SU8 layer to facilitate the slide removal after the nsPEFs application.

Considering the first design (Fig. 1.(b)i.), cells are separated from the electrodes, and disposed at a distance controlled by micropillars height (H) which are microfabricated in thick resist. Hence, this structure includes 25 µm-high gold electrodes, and 50 µm-high SU8 micro-pillars.

The second design (Fig. 1.(b)ii.), which was finally chosen for the experiments, possesses the same 25 µm thick electrodes, on which the removable slide covered with adherent cells is directly apposed. In that case, the length of the electrodes was adjusted (L=3 cm) to achieve the impedance matching, taking into account the thickness (tc≈7 µm) of the cell layer cultured on the cover slide, and the conductivity (σ=1.55 S/m) of the medium used. The thickness of the cell layer was estimated from the geometrical properties of DC3F cells (the cell type used in our experiments), and was confirmed by the actual measured impedance (see next section).

Once the culture slide is positioned in the SU8 frame, two spring strips are used to maintain it on the biochip.

Spatial homogeneity of the applied electric field pulses:

The culture slide being positioned above the metallic electrodes, as shown on Figure 1(b), the amplitude of the electric field depends on the location within the channel section. Hence, it is necessary to quantify the electric field attenuation to validate the feasibility of the cell nanoporation in this configuration. On Figure 2.(a), we compared the field distribution in the two design cases (with or without the 50µm resist pillars), using finite element analysis simulations performed with Comsol. We considered the thickness tc of the cell layers. ) in the microfluidic chamber. The cell layer cultured on the cover slide, is confined between altitudes z=50-57 µm in the case of prototype 1 and z=25-32 µm for prototype 2 (considering the cell thickness does not exceed tc=7 µm). This analysis shows that the variation of the electric field in a section of the microchannel remains quite acceptable in both structures, but that the best homogeneity (Table 1) is achieved with design 2 (without micro-pillars).

Homogeneity of the electric field as a function of the z position in the microchamber

Homogeneity of the electric field as a function of the x position in the microchamber, over 90% of the distance between the electrodes Central position (0 µm) Design 2 (25 µm thick electrodes, no thick resist pillars) seems to be the most appropriate design, if the field homogeneity criteria in the microchannel is considered as the most important criterion (Figs. 2.(a)ii., 2.(b), and Table 1).

Nevertheless, the design 1 (involving the 50 µm resist pillars) has the advantage to prevent any contact between the cells and the electrodes. Indeed, such contact might alter the cell viability (due to electric field edge effects visible on figure 2.(b)ii.).

B. Fabrication process

Both proposed designs were fabricated on a quartz substrate, as it is transparent, has good dielectric properties and presents good adhesion properties. The materials used for the fabrication are biocompatible. The metallic electrodes are in electroplated gold as it is biocompatible and has a good conductivity (sigma=4.1x10 7 S/m). The microfluidic chamber is patterned with a thick photosensitive resist (SU8, MicroChem), broadly used in bio-microfluidic devices. The process started with a quartz substrate (from ACM), which was premetallized with a Cr/Au layer whose thickness was respectively 30 nm/150 nm. After a cleaning of the wafer with successively acetone, isopropanol, water baths and desorption at 150°C, the gold thickness was increased up to 25 µm. The gold was electroplated using an KAu(CN)2 bath and a current density of 1.5 mA/cm 2 . The gold electrodes were then patterned using UV photolithography of S1805 resist, followed by gold and chromium chemical etching. The microchamber was then fabricated on the electrodes by the structuring of a SU8 layer using photolithography. Concerning the SU8 pillars design (prototype 1), a double SU8 layer was used to define the 50 µm thick pillars and the 100 µm thick SU8 frame. The first SU8 layer (SU8 2025) was spin coated to reach a thickness of 50 µm (1700 rpm for 30 s), baked (3 min at 65°C and 15 min at 95°C), exposed to UV (390 mJ/cm 2 ) and post exposure baked (3 min at 65°C and 15 min at 95°C). The second SU8 layer (SU8 2075) was then spin coated to reach a final thickness of 100 µm (2100 rpm for 30 s). The resist was baked (3 min at 65°C and 15 min at 95°C), exposed again (600 mJ/cm 2 ), post exposure baked (3 min at 65°C and 15 min at 95°C) and the two layers were simultaneously developed. Considering prototype 2 (without the pillars), only one layer of SU8 (SU8 2075) was spin coated to directly reach the targeted thickness of 100 µm (2100 rpm for 30 s). The resist was then baked (5 min at 65°C and 20 min at 95°C), exposed to UV (600 mJ/cm 2 ) and post exposure baked (3 min at 65°C and 15 min at 95°C). The SU8 layer was finally developed to define the microfluidic chamber. Figure 3 shows photographs of the fabricated biochips.

C. Cell preparation DC-3F cells (Chinese hamster lung fibroblast cells) were grown in MEM (Minimum Essential Medium) supplemented with 10% fetal bovine serum, 100 U/mL penicillin and 100 µg/mL streptomycin. Cells were propagated at 37°C in a humidified 5% CO2 atmosphere. Cells were routinely passed every two days. All the chemicals were purchased from Invitrogen (Cergy Pontoise, France).

For the biological experiments, cells were cultured on glass slides for at least 4 hours. In order to visualize the effect of nsPEFs on living cells, the slides were incubated for 30 min with the fluorescent calcium marker Fluo-4 AM (λex=496 nm, λem=515 nm) in a humidified atmosphere with 5% CO2 at 37 °C. The slides were washed three times with PBS and placed on the top of the chip (the cells being thus located inside the channel). Fluo-4 AM dye possesses acetoxymethyl groups (AM) allowing the molecule to enter the cells and preventing calcium binding outside of the cell. Once the marker is inside the cytoplasm, the AM groups are cleaved by endogenous esterases resulting in both the trapping of the fluorophore and its activation. If the cytosolic calcium concentration increases, Fluo-4 fluorescence increases. Hence, monitoring the fluorescence of exposed cells allows knowing if organite membranes or plasma membranes are affected by the nsPEF and become permeable to the calcium ions. Cells were exposed to a single 10 ns pulse of 280 kV/cm. DC-3F cell images were taken with a Zeiss AxioCam Hrc camera on a Zeiss Axiovert S100 epifluorescence inverted microscope controlled through the Axio Vision 4.6 software (Carl Zeiss, Germany).

D. Electrical set-up: nanosecond pulse generator and measurement

A commercial generator purchased from FID (FID GmbH, Model FPG 10-ISM10, Burbach, Germany) with an output impedance of 50 Ω was used to treat the cells. It generates trapezoidal monopolar pulses with a full-width at half maximum of 10 ns [START_REF] Dalmay | Design and realization of a microfluidic device devoted to the application of ultra-short pulses of electrical field to living cells[END_REF][START_REF] Silve | Nanosecond-duration electric pulse delivery in vitro and in vivo: experimental considerations[END_REF][START_REF] Silve | Nanosecond pulsed electric field delivery to biological samples : difficulties and potential solutions[END_REF]. The output voltage magnitude goes from 3 kV to 10 kV. The rising edge lasts between 0.4 and 0.6 ns. The falling edge lasts between 1 and 1.5 ns.

In order to characterize the incident and reflected signals in the exposure set-up, a tap-off (245 NMFFP-100, Barth Electronics Technology, USA) was connected between the generator and the biochip using two transmission lines [START_REF] Kenaan | Characterization of a 50 Ohms Exposure Set-up for High Voltage Nanosecond Pulsed Electric Field Bioexperiments[END_REF]. The tap-off is a threeport device. The impedance of the mainline (i.e. the nsPEF-biochip line) is 50 Ω whereas the impedance of the measurement port (i.e. the connection to the oscilloscope) is 4950 Ω, allowing a voltage measurement with a 1:100 ratio. A Wavemaster 808Zi 8GHz oscilloscope (LeCroy, Courtaboeuf, France) has been used for the measurements.

III. Results and Discussion

Optimum architectures of the device have been investigated in order to ensure a good homogeneity of the cells exposure conditions within the microfluidic channel. Indeed, for this study concerning nsPEFs effects on adherent cells, that are attached on glass cover slides reported on the nanoporation device, nsPEFs should be very well controlled and spatially homogeneous.

As shown by finite element analysis, the homogeneity of the electric field is enhanced when the culture slide is directly reported on the 25 µm thick electrodes (prototype 2), as far as we examine cells that are not directly in contact with the electrodes. The 25 µm thick electrodes structure combined to 50 µm resist pillars (Prototype 1) gives satisfying but lower homogeneity for the electric field as explained in section II.A. Therefore the prototype 2 (25 µm thick electrodes, no pillars) has been employed to achieve the results presented thereafter. To validate the possibility to expose cells reported on the top of the electrodes, biological experiments have been achieved and especially, we study the dynamics of the [Ca2+]i in response to the application of nsPEF. DC-3F cells were loaded with the calcium marker Fluo-4 AM. Cells were exposed to a single 10 ns pulse of 280 kV/cm. The profile of applied nsPEFs is reported in figure 4. As predicted, a good impedance matching is achieved; around 5 % of the nsPEF is reflected back to the nanopulser which gives an effective impedance of the chip equal to 45 Ω. This slight difference could be interpreted as an under-estimation of the cell layer height or some inhomogeneities in this height.

Concerning the cell exposure, recording started 100 s before the pulse, to visualize the baseline of the fluorescence, and continued for 10 min after the nanopulse delivery. Figure 7 reports typical results achieved under the experimental conditions reported here. As seen on the figure 5.(a), an increase in the Fluo-4 fluorescence in the presence of extracellular calcium, indicating a raise in the cytosolic calcium concentration, was observed. After 400 s the fluorescence was back to the baseline showing that the cells can recover this massive calcium release, probably through the activation of pumps and transporters. An original microfluidic device dedicated to the application of nsPEFs to adherent cells and their real time monitoring has been developed and characterized in this work. The proposed device involves a removable packaging. Indeed, with such a packaging, the preparation of cell cultures on standard commercial slides remains possible, these slides being afterwards reported on the device for the nanopulses exposition and cell monitoring experiments. Two approaches have been compared in terms of microfabrication process and electric field homogeneity achieved in the microfluidic chamber. The efficiency of our device has been demonstrated with a successful study of the dynamics of the [Ca 2+] i in response to the application of nsPEF. The effect of extremely high amplitude and short duration electric pulses (280 kV/cm, 10 nS) that could be applied for the first time to adherent cells, were recorded in real time in our microdevice. Kinetics of calcium responses show an increase in fluorescence due to the nanopulse application.

These promising results pave the way for the development of micro and nano systems well adapted to a better understanding of nanoporation effects on living cells.

Figure 1 :

 1 Figure 1: (a) Schematic representation of the device, involving electroplated gold electrodes in a transmission line configuration, and a thick SU8 resist frame for the centering of the removable glass

Figure 2 :

 2 (a) Electric field calculation by finite element analysis, for the two designs developed for the nanoporation of adherent cells: (i) Design with the 50 µm resist pillars and (ii) Design without the micropillars. The cell layer is taken into account (estimated at tc=7 µm). (b) Homogeneity of the electric field within the nanoporation channel (for 1 V): (i) depending on the z position in the microfluidic chamber and (ii) depending on the x position of cells on the glass slide (from one electrode side to the other). Blue curves correspond to design 1 (with micro-pillars), while red curves correspond to design 2 (without pillars).

Figure 2 .

 2 Figure 2.(b) displays the electric field dependence on the z position (Fig.2(b)i.) and the x position (Fig.2.(b)ii.) in the microfluidic chamber. The cell layer cultured on the cover slide, is confined between altitudes z=50-57 µm in the case of prototype 1 and z=25-32 µm for prototype 2 (considering the cell thickness does not exceed tc=7 µm). This analysis shows that the variation of the electric field in a section of the microchannel remains quite acceptable in both structures, but that the best homogeneity (Table1) is achieved with design 2 (without micro-pillars).

Figure 3 :

 3 Figure 3: Photographs of the fabricated microfluidic devices. (a) prototype 1, with SU8 microstructured pillars and (b) prototype 2 without pillars; (c) general view of the device connected to the PCB (printed circuit board), with two springs to maintain the culture slide.

Figure 4 :

 4 Figure 4: recording of the applied nsPEFs

Figure 5 :

 5 Figure 5: (a) Real time imaging of a calcium peak from cells imaged every 10 s with a 500 ms exposure. Attached DC-3F cells were loaded with the calcium marker Fluo-4 (5 µM). A single 10 ns pulse of 280 kV/cm was delivered. A: 8 s before the nanopulse. B: 2 s after the nanopulse. C: 40 s after the nanopulse. D: 600 s after the nanopulse and (b) kinetics of the calcium response of the three cells observed in the previous figure

Table 1 :

 1 Spatial homogeneity of the electric field.

			Side position	In contact with	tc (7 µm)
			(+/-50 µm)	the cover	below the
					cover
	Design 1	2.85%	21. 9%	28.9%	27.1%
	Design 2	0.02%	1.55%	10.6%	2.01%

V. Acknowledgments

This work was supported by the French National Agency through Nanoscience and Nanotechnology Program (Nanopulse-biochip n• ANR-08-NANO-024), CNRS, ENS de Cachan, Institut Gustave Roussy, University Paris-Sud, PRES Universud and CNANO'Ile de France.


Adrien Couëtoux

Jean-Baptiste Hoock

Nataliya Sokolovska

Olivier Teytaud

Nicolas Bonnard

Continuous Upper Confidence Trees

Upper Confidence Trees are a very efficient tool for solving Markov Decision Processes; originating in difficult games like the game of Go, it is in particular surprisingly efficient in high dimensional problems. It is known that it can be adapted to continuous domains in some cases (in particular continuous action spaces). We here present an extension of Upper Confidence Trees to continuous stochastic problems. We (i) show a deceptive problem on which the classical Upper Confidence Tree approach does not work, even with arbitrarily large computational power and with progressive widening (ii) propose an improvement, termed double-progressive widening, which takes care of the compromise between variance (we want infinitely many simulations for each action/state) and bias (we want sufficiently many nodes to avoid a bias by the first nodes) and which extends the classical progressive widening (iii) discuss its consistency and show experimentally that it performs well on the deceptive problem and on experimental benchmarks. We guess that the double-progressive widening trick can be used for other algorithms as well, as a general tool for ensuring a good bias/variance compromise in search algorithms.

Introduction

Monte-Carlo Tree Search [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF] is now widely accepted as a great tool for highdimensional games [START_REF] Lee | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF] and high-dimensional planning [START_REF] Nakhost | Monte-carlo exploration for deterministic planning[END_REF]; its most well known variant is Upper Confidence Trees [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. It is already adapted to continuous domains [START_REF] Rolet | Optimal robust expensive optimization is tractable[END_REF][START_REF] Rolet | Optimal active learning through billiards and upper confidence trees in continous domains[END_REF], but not for arbitrary stochastic transitions; this paper is devoted to this extension.

In section 2, we will present Progressive Widening (PW), a classical improvement of UCT in continuous or large domains. We will see that PW is not sufficient for ensuring a good behavior in the most general setting; a simple but not trivial modification, termed double-PW, is proposed and validated. Experiments (section 3) will show that this modification makes UCT for Markov Decision Processes compliant with high-dimensional continuous domains with arbitrary stochastic transition.

In all the paper, #E denotes the cardinal of a set E.

Progressive strategies have been proposed in [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF][START_REF] Chaslot | Progressive Strategies for Monte-Carlo Tree Search[END_REF] for tackling problems with big action spaces; they have been theoretically analyzed in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF], and used for continuous spaces in [START_REF] Rolet | Optimal active learning through billiards and upper confidence trees in continous domains[END_REF][START_REF] Rolet | Optimal robust expensive optimization is tractable[END_REF]. We will here (i) define a variant of progressive widening (section 2.1), (ii) show why it can't be directly applied in some cases (section 2.2), (iii) define our version (section 2.3).

Progressive widening

Consider an algorithm, choosing between options O = {o 1 , o 2 , . . . , o n , . . . } at several time steps. More formally, this is as follows:

R 0 = 0 for t = 1, t = 2, t = 3, . . . do Choose an option o (t) ∈ O.

Test it: get a reward r t . Cumulate the reward: R t = R t-1 + r t . end for

The goal is to design the "Choose" method so that the cumulated reward increases as fast as possible. An option (terminology of bandits) is equivalent to an action (terminology of reinforcement learning) or a move (terminology of games).

Many papers have been published on such problems, in particular around upper confidence bounds [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF]. Upper Confidence Bounds, in its simplest version, proceeds as follows:

Upper confidence bound algorithm with parameter k. R 0 = 0 for t = 1, t = 2, t = 3, . . . do Choose an option o (t) ∈ O maximizing score t (o) defined as follows:

totalReward t (o) = 1≤l≤t-1,o l =o r l nb t (o) = 1≤l≤t-1,o l =o 1 score t (o) = totalRewardt(o) nbt(o)+1 + k ucb log(t)/(nb t (o) + 1) (+∞ if nb t (o) = 0) Test it: get a reward r t . Cumulate the reward: R t = R t-1 + r t . end for
Variants of the score function are termed "bandit algorithms"; there are plenty of variants of the score formula; this is essentially independent of the aspects investigated in this paper.

A trouble in many mathematical works around such problems is that the set O is usually assumed small in front of the number of iterations. More precisely, the behavior of the algorithm above is trivial for t ≤ #O. [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF] proposed the use of a constant s such that nb t (o) = 0 ⇒ score t (o) = s; this is the so-called First Play Urgency algorithm. There are other specialized efficient tools for bandits used in "trees" such as rapid action value estimates [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF][START_REF] Finnsson | Simulation-based approach to general game playing[END_REF]; however these tools assume some sort of homogenity between the actions at various time steps. [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF][START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF][START_REF] Chaslot | Progressive Strategies for Monte-Carlo Tree Search[END_REF] proposed progressive strategies for big/infinite sets of arms. The principle is as follows for some constants C > 0 and α ∈]0, 1[ (as it is independent of the algorithm used for choosing an option, within a given pool of possible options, we do not explicitly write a score function as above):

Progressive widening with constants C > 0 and α ∈]0, 1[. The key point is that the chosen option is restricted to have index ≤ k; the complete set O = {o 1 , o 2 , . . . } is not allowed. This algorithm has the advantage that it is anytime: we do not have to know in advance at which value of t the algorithm will be stopped. [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF] applied it successfully in the very efficient CrazyStone implementation of Monte-Carlo Tree Search [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF]. Upper Confidence Tree (or Monte-Carlo Tree Search) is not a simple setting as above: when applying an option, we reach a new state; one can think of Monte-Carlo Tree Search (or UCT) as having one bandit in each possible state s of the reinforcement learning problem, for choosing between (infinitely many) options o 1 (s), o 2 (s), . . . , o n (s), . . . . The algorithm is as follows, for a task in which all the reward is obtained in the final state 3 . The last line of the algorithm (returning the most simulated action from S) is often surprising for people who are not used to MCTS; it is known as much better than choosing the action with best expected reward.

R 0 = 0 for t = 1, t = 2, t =
Progressive Widening (PW) applied in state s with constants C > 0 and α ∈]0, 1[. Input: a state s. Output: an action. Let nbV isits(s) ← nbV isits(s) + 1 and let t = nbV isits(s) Let k = ⌈Ct α ⌉. Choose an option o (t) (s) ∈ {o 1 (s), . . . , o k (s)} maximizing score t (s, o) defined as follows:

totalReward t (s, o) = 1≤l≤t-1,o l (s)=o r l (s) nb t (s, o) = 1≤l≤t-1,o l =o 1 score t (s, o) = totalRewardt(s,o) nbt(s,o)+1 + k ucb log(t)/(nb t (s, o) + 1) (+∞ if nb t (o) = 0) Test it: get a state s ′ .

UCT algorithm with progressive widening

Input: a state S, a time budget. Output: an action a. Initialize: ∀s, nbSims(s) = 0 while Time not elapsed do // starting a simulation. s = S. while s is not a terminal state do Apply progressive widening in state s for choosing an option o. Let s ′ be the state reached from s when choosing action o. s = s ′ end while // the simulation is over; it started at S and reached a final state. Get a reward r = Reward(s) // s is a final state, it has a reward. For all states s in the simulation above, let r nbV isits(s) (s) = r. end while Return the action which was simulated most often from S.

It is important to keep in mind that the progressive widening algorithm is applied in each visited state; some states might be visited only once, or never, and some other states are visited very often. MCTS with progressive widening or progressive strategies is the only version of MCTS which works in continuous action spaces [START_REF] Rolet | Optimal robust expensive optimization is tractable[END_REF][START_REF] Rolet | Optimal active learning through billiards and upper confidence trees in continous domains[END_REF]; however, it was applied only with the property that applying a given action a in a given state s can lead to finitely many states only. We will see in section 2.2 that this methodology (the algorithm above) does not work as is in the case in which there is a null probability of reaching twice the same state when applying the same action in the same state (i.e. typically it does not work for stochastic transitions with continuous support).

Why it does not work as is for randomized transitions in continuous domains

We have presented UCT with progressive widening. In this section we will show why it is not sufficient for a consistent behavior (i.e. for a convergence toward maximum expected reward) in some cases, in particular when the transitions are stochastic and never lead twice to the state -one can think of the case of a Gaussian additive noise, or any other noise such that states can be reached only once.

Let us assume now that we have an infinite (discrete or continuous) domain of options. This is not too much a trouble for progressive widening: if α ∈]0, 1[, and if the o t are a good approximation of the set of possible actions (typically, in continuous domains, we assume that the set {o i ; i ≥ 1} is dense in the set of actions and the reward has some smoothness properties), then asymptotically, good actions are explored, and all these explored actions are sampled infinitely often [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF].

Let us now consider what happens if we have randomized transitions. Assume that for a state s and an action a, we can reach infinitely many transitions. Consider such a state s, and assume that we visit it infinitely often; we would like the algorithms to have two characteristics:

1. infinitely many actions (a 1 , α 2 , a 3 , . . . ) will be explored (for reducing the bias due to the choice of actions); 2. all states that can be reached from s are themselves explored infinitely often (for reducing the variance due to random exploration).

We do not have a mathematical proof that these two requirements are enough, but they look quite reasonnable: in order to approximate a continuous set of actions, and unless we have an efficient pruning to a finite set of actions, we will have to explore infinitely many actions; and if we consider only finitely many possible consequences of an action whereas the real support is infinite we will miss important facts and it is hard to believe that the algorithm can be consistent.

For classical score functions, progressive widening will ensure the first property. But the second property will not be ensured, as in continuous domains with stochastic transitions, nothing ensures that we will reach twice the same state, whenever we play infinitely often a given action a in a given state s. This will be illustrated on the Trap problem later.

The following section is devoted to proposing a solution to this problem.

Proposed solution: double progressive widening

Section 2.1 has presented the known form of progressive widening, and section 2.2 has shown that in some cases it does not work (namely, when there are pairs (s, a) such that, with probability one, applying a in s infinitely often does not lead to visiting the following states infinitely often). In this section, we propose the use of a second form of progressive widening in MCTS, as follows: // the simulation is over; it started at S and reached a final state. Get a reward r = Reward(s) // s is a final state, it has a reward. For all states s in the simulation above, let r nbV isits(s) (s) = r. end while Return the action which was simulated most often from S. This algorithm is not so intuitive, for the second progressive widening part. The idea is as follows:

totalRewardt(s, o) = 1≤l≤t-1,o l (s)=o r l (s) nbt(s, o) = 1≤l≤t-1,o (l) (s)=o 1 scoret(s, o) = totalReward t (s,o) nb t (s,o)+1 + k ucb log(t)/(nbt(s, o) + 1) (+∞ if nbt(o) = 0) Let k ′ = ⌈Cnbt(s, o (t) (s)) α ⌉ if k ′ > #Childrent(s, o (t) (s)) //
-If k ′ is large enough, we consider adding one more child to the pool of visited children: we simulate a transition and get a state s ′ . If we get an already visited child, then we go to this child; otherwise, we create a new child. -If k ′ is not large enough, then we sample one of the previously seen children.

As they are not necessarily equally likely, we select a child proportionally to the number of times it has been generated.

The algorithm has been designed with a "consistency" objective in mind, which is twofolds:

-Infinite visiting: we want that if a node is visited infinitely often, then we generate infinitely many children, and each of these children is itself visited infinitely often. By induction, this property ensures that all created nodes are visited infinitely often. Progressive widening and the UCB formula (or many other formulas in fact) ensure this property. -Propagation: the average reward of any node visited infinitely often converges to a limit and this limit (for a non-terminal node) is the average reward corresponding to its children which have best asymptotic average reward. This property is ensured by the careful sampling in the progressive widening.

Experiments

In section 3.1 we present a deceptive problem designed specifically for pointing out the inconsistency of the classical PW approach. In section 3.2 we treat a more real problem.

Trap problem

In this section we present the toy problem, aimed at being (i) deceptive for the simple progressive widening (ii) as simple as possible. We provide our experimental results as well.

Problem description. This problem has been designed to clearly illustrate the weakness of the simple progressive widening. In this problem, one has to make two successive decisions, in order to maximize the reward. As we will see, the optimal policy is to make a risky move at the first step, in order to be able to obtain the maximum reward on the second (and last) step. The state will be denoted x, and is initialized at x 0 = 0. At each time step t the decision is denoted d t ∈ [0, 1]. Let R > 0 be the noise amplitude at each time step. At a time step t, given the current state x t and a decision d t , we have:

x t+1 = x t + d t + R × Y,
Y being a random variable following a uniform distribution on [0, 1].

The trap problem relies on five positive real numbers: the high reward h, the average reward a, the initial ramp length l, and the trap width w. The high reward will be given if and only if we cross the trap, otherwise we obtain 0. If we stay on the initial ramp, we get the average reward. We thus define the reward function r(•) as follows:

r(x) =    a if x < l 0 if l < x < l + w h if x > l + w
The objective is to maximize r(x 0 ) + r(x 1 ), the cumulated reward. The shape of the reward function is shown in Fig. 1. Experimental results. We compare simple progressive widening and double progressive widening on the trap problem. In our experiments, we used the following settings: a = 70, h = 100, l = 1, w = 0.7, R = 0.01. With these parameters, the optimal behavior si to have the first decision d 0 ∈ [0.7, 1] and d 1 ≥ 1.7 -d 0 . If one makes optimal decisions, one has an expected reward of r * = 170. That is the reward toward which the Double progressive widening version of Monte Carlo Tree Search converges. However, the Simple progressive widening version does not reach this optimal reward. Worse, as we increase the computation time, it becomes less efficient, converging toward a local optimum, 140.

The mean values of the rewards are shown in Fig. 2 and the medians of the rewards are shown in Fig. 3. Each point is computed according to 100 simulations.

The power management problem

In this section we present a real world problem. We show our experimental results for various settings of the power management problem.

Problem description. The experimental setup is an energy stock management problem. We have finitely many energy stocks (nuclear stocks, water stocks), each of them can be used to produce electricity; we can also produce electricity with classical thermal plants, that are more costly. The problem is to find the right tradeoff between using stocks now (in order to save up money), with the risk that later we might have peaks of demands, leading to very high costs if we do not have enough stocks. -keeping stocks for later (in order to avoid the trouble above), with the risk that we might have too much in a stock if there is no big peak of demand.

Also, even for a fixed amount of water used from the stocks, we have to decide which stock we want to use. In particular, stocks above a given level are lost (because we have to get rid of water when the level is too high). All stocks are not equivalent: some of them have stronger inflows than others, and the used part of some stocks is transfered to other stocks whereas others are not or not to the same. One can think of a graph of reservoirs, water used in a given stock being forwarded to another stock given by the graph. In our implementation, the demand is a function of the time, determined in advance. The inflows, however, follow a lognormal distribution. Hence, they take different values from one simulation to the other. The code of the problem can be found in http://www.lri.fr/ ~couetoux/ stock.cpp or requested by email.

Small size experiments. We consider here 2 stocks only and 5 time steps. We compare the Q-learning algorithm from the Mash project http: //mash-project.eu/, our progressive widening Monte-Carlo Tree Search approach, a greedy algorithm only maximizing the short term, and a blind planner optimizing a sequence of decisions regardless of stock levels. Results are presented in Fig. 4. We plot the median values of cumulated reward as a function of time. It is easy to see that the Simple and Double PW MCTS achieve the best performance, compared to Blind, Greedy, and Q-learning approaches. In this particular (power management) problem, decisions are strongly associated with stock levels (states). The performance of the Blind is poor, since it makes illegal decisions rather often. Our implementation of the Q-learning suffers from the same phenomenon. Bigger size experiments. We here switch to 6 stocks and 21 time steps, corresponding to 3 time steps per day, one week, with an expected increase of demand at some point during the week. Results are presented in Fig. 5. Note, that the conclusion is the same as for the small scale problem, described above: the proposed Simple and Double PW MCTS are very competitive compared to other tested methods. We did not include the results of the Q-learning. In this setting, the Q-learning obtained rather poor rewards. For the sake of clarity of results of other approaches, we do not show the performance of the Q-learning on Fig 5.

Conclusion

We have modified progressive widening in order to make it compliant with continuous domains with general noise. Experimentally, the "double-PW" modification was very efficient on deceptive problems aimed at pointing out the weaknesses of simple PW; we conjecture that for some problems, both versions are roughly equivalent, and for some problems the double PW is much better. On the other hand, on a realistic problem, the modification had disappointingly little effect. The formal proof of the consistency of the double PW (i.e. the convergence to the optimal reward for wide classes of Markov Decision Processes) has not been given and is the main further work.

Fig. 1 .

 1 Fig. 1. Shape of the reward function: Trap problem.

Fig. 2 .

 2 Fig. 2. Mean of the reward, for the trap problem with a = 70, h = 100, l = 1, w = 0.7, R = 0.01. The estimated standard deviations of the rewards are ST DDP W = [13.06, 12.88, 12.88, 12.06, 14.70, 0, 0] for Double PW and ST DSP W = [7.16, 7.16, 8.63, 9.05, 0, 0, 0] for Simple PW -the differences are clearly significant, where ST D means standard deviation.

Fig. 3 .

 3 Fig. 3. Median of the reward, for the trap problem with a = 70, h = 100, l = 1, w = 0.7, R = 0.01

Fig. 4 .

 4 Fig. 4. The power management problem. Median values of cumulated reward with 2 stocks and 5 time steps.

Fig. 5 .

 5 Fig. 5. The power management problem. Median values of cumulated reward. Experiments with 6 stocks and 21 time steps.

  3, . . . do Let k = ⌈Ct α ⌉. Choose an option o (t) ∈ {o 1 , . . . , o k }. Test it: get a reward r t . Cumulate the reward: R t = R t-1 + r t . end for

  Let k = ⌈Ct α ⌉.Choose an option o (t) (s) ∈ {o1(s), . . . , o k (s)} maximizing scoret(s, o) defined as follows:

	Double Progressive Widening (DPW) applied in state s with constants
	C > 0 and α ∈]0, 1[.
	Input: a state s.
	Output: a state s ′ .
	Let nbV isits(s) ← nbV isits(s) + 1
	and let t = nbV isits(s)

This assumption (that the reward is null except in the final state) simplifies the writing, but is not necessary for the work presented here.

Acknowledgements

We are grateful to the IOMCA project (ANR) and the FP7 program (Mash project) for support.


Adrien Couëtoux

Hassen Doghmen

Adding Double Progressive Widening to Upper Confidence Trees to Cope with Uncertainty in Planning Problems

Keywords:

Current state of the art methods in energy policy planning only approximate the problem (Linear Programming on a finite sample of scenarios, Dynamic Programming on an approximation of the problem, etc). ) seems to be a potential candidate to converge to an exact solution of these problems ([2]). But how fast, and how do key parameters (double/simple progressive widening) influence the rate of convergence (or even the convergence itself), are still open questions. Also, MCTS completely ignores the features of the problem, including the scale of the objective function. In this paper, we present MCTS, and its extension to continuous/stochastic domains. We show that on problems with continuous action spaces and infinite support of random variables, the "vanilla" version of MCTS fails. We also show how the double progressive widening technique success[2] relies on its widening coefficient. We also study the impact of an unknown variance of the random variables, to see if it affects the optimal choice of the widening coefficients.

Introduction

Monte Carlo Tree Search methods have given promising results on high dimensional stochastic planning problems [START_REF] Nakhost | Monte-carlo exploration for deterministic planning[END_REF] in continuous domains [START_REF] Rolet | Optimal active learning through billiards and upper confidence trees in continous domains[END_REF][START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF]. Among the many potential applications, we consider the field of energy policies. The quality of energy policies has a huge financial and ecological impact. Also, resources being limited, power generation is relying increasingly on renewable energies. These energies (water stocks, solar panels, etc) are subject to high variations, and cannot be adjusted on demand. Thus, there is a growing need for a smart planning of how we use them. The current state of the art methods used in the industry mostly relies on approximations of the real problem, and fail to cope with an increase in the dimension of the state space. MTCS methods present the advantage of dealing with the exact problem. They also do not require any expert knowledge about the problem itself, and have been known to be quite robust with respect to an increase in the dimension of the state space.

In [START_REF] Bjarnason | Lower Bounding Klondike Solitaire with Monte-Carlo Planning[END_REF], it is shown that, when using UCT-based algorithms in a domain where the transition is stochastic, it is important to control the number of different random outcomes to explore for each couple state/action. In the case of the Klondike game, their experiments show that it is better to explore about 5 different random outcomes per couple state/action, in comparison with exploring only 1 outcome, or 10 outcomes. Depending on the number of random outcomes explored, the performances of UCT-based algorithm vary significantly. The authors also suggest that a progressive widening technique could be interesting, instead of a fixed sampling width. This idea seems particularly relevant, especially in domains where the stochastic elements of the transition have a continuous support. Such technique has already been introduced in [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF]. In this paper, the authors show how the original version of MCTS fails to converge towards the optimal solution in stochastic and continuous domains. They propose a solution to this issue, called Double Progressive Widening. Instead of limiting the number of explored random outcomes of each couple state/action, this technique progressively widens the tree at each node, according to the number of simulations of these nodes. However, this method still relies on two parameters, that remain to be tuned.

The first part of this paper (Section 2) will present the MCTS algorithm, as well as the Double Progressive Widening technique. We illustrate its efficiency on a simple stock problem, with a small stochastic part. The second part of this paper (Section 3) is devoted to the impact of the parameters of the Double Progressive Widening. We observe that, although the best set of parameters can vary across different problems, some settings are safe, and can guarantee reasonable performances, independently of the distribution of the random events.

Experiments on a basic stock problem

In this section, we study the impact of Double Progressive Widening (DPW) on the MCTS algorithm. We compare it to the standard Simple Progressive Widening MCTS (MCTS-SPW) on a basic stock problem. Let us first remind the MCTS algorithm, along with the double progressive widening technique, as introduced in [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF].

MCTS with double progressive widening (DPW)

We consider a standard sequential decision making problem under uncertainty. The decision maker has to choose an action at every time step, until he reaches the horizon, where the reward is computed. We will note S the state space, D the decision space, and H the horizon. At each time step, the decision maker is given an initial state, and must return a decision. The goal of the decision maker is to find a policy that, given an initial state, returns the decision that maximizes the expected reward.

The MCTS algorithm explores some of the reachable states, by building a tree. Its nodes represent the states. The root of the tree is the initial state. The MCTS algorithm runs for a given time budget, and then returns a decision. The core of this algorithm lies in the way the tree is built. It aims at progressively exploring new states, by trying new decisions, while still exploiting the already explored states. The balance between exploration and exploitation is ensured by the Double Progressive Widening.

The core of the algorithm can be divided into four distinct phases, as shown in Fig. 1. First, we navigate through the already constructed nodes of the tree (selection phase). Then, when we decide to explore a new state, from the node that we reached, we try a new decision (expansion phase). Then, we simulate a series of decisions until we reach a final state (simulation phase). Finally, we compute the reward corresponding to the final state we just reached, and back propagate the information along the path that led to this state (propagation phase).

The Progressive Widening is the technique that defines when we decide to end the selection phase. More precisely, it defines when we decide to explore new states (i.e. add nodes to the tree), and when we decide to exploit known states.

The basic version of MCTS, as seen in [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF], will be reffered to as MCTS with Simple Progressive Widening (MCTS-SPW). This method is suitable to deterministic problems. As we will see, it is inefficient on stochastic problems, even when the random part has a very small impact on the reward function.

What follows, is the formal description of MCTSwith Double Progressive Widening (MCTS-DPW), as seen in [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF].

Double Progressive Widening (DPW) applied in state s with constants C > 0, α ∈]0, 1[, and β ∈]0, 1[. Input: a state s. Output: a state s ′ . Let nbV isits(s) ← nbV isits(s) + 1 and let t = nbV isits(s)

Let k = ⌈Ct α ⌉. Choose an option o (t) (s) ∈ {o1(s), . . . , o k (s)} maximizing scoret(s, o) defined as follows: totalRewardt(s, o) = 1≤l≤t-1,o l (s)=o r l (s) nbt(s, o) = 1≤l≤t-1,o (l) (s)=o 1 scoret(s, o) = totalReward t (s,o) nbt(s,o)+1 + k ucb log(t)/(nbt(s, o) + 1) (+∞ if nbt(o) = 0) Let k ′ = ⌈Cnbt(s, o (t) (s)) β ⌉ if k ′ > #Childrent(s, o (t) (s)) // progressive widening on the random part then Test option o (t) (s); get a new state s ′ if s ′ ∈ Childrent(s, o (t) ) then Childrent+1(s, o (t) ) = Childrent(s, o (t) ) ∪ {s ′ } else Childrent+1(s, o (t) ) = Childrent(s, o (t) ) end if else Childrent+1(s, o (t) ) = Childrent(s, o (t) ) Choose s ′ in Childrent(s, o (t) ) // s ′ is chosen with probability nbt(s, o, s ′ )/nbt(s, o) end if
UCT algorithm with DPW Input: a state S. Output: an action a. Initialize: ∀s, nbSims(s) = 0 while Time not elapsed do // starting a simulation. s = S. while s is not a terminal state do Apply DPW in state s for choosing an option o. Let s ′ be the state given by DPW. s = s ′ end while // the simulation is over; it started at S and reached a final state. Get a reward r = Reward(s) // s is a final state, it has a reward. For all states s in the simulation above, let r nbV isits(s) (s) = r. end while Return the action which was simulated most often from S.

Energy stock problem with low stochasticity

We first experiment MCTS on a basic energy stock management problem, defined as follows. There are N stocks, and at every time step, we have to decide how much energy is taken from each stock. These stocks can be water reservoirs, and can be connected to each other. We consider the case where they lay in a valley: the water taken out of the first stock goes into the second, and so on, and the water taken out of the last stock is lost in the ocean. There is also a thermal plant, that has a given maximum production capacity. Producing energy from the water stocks is free (although the stocks are finite), and using the thermal plant has a cost, quadratic in the amount of energy produced. At each time step, each stock receives an extra inflow (from the rain), that follows an unknown random distribution. The goal of the decision maker is to satisfy a time varying demand, at the lowest possible cost.

In this first section, we consider the case where the inflows are small, relatively to the stocks and the demand. It is important to note that, since the MCTS does not measure any distances, having a relatively small random part in our problem does not help much the algorithm.

As we will see, even adding an infinitesimal random part in the transition, as long as the support of the distribution is continuous, causes a lot of trouble to a basic version of MCTS.

Our experiment was made on a problem with 2 stocks and 6 time steps. The initial stock level was set to 100. The thermal plant had a maximum production capacity of 50 per time step. The average demand per time step was of 75 (it varies over time, to reflect the seasonality of the energy consumption). The inflows on each stock were uniformly distributed on [0, 1].

We compared the performances of four algorithms. First, the original version of MCTS in continuous domains (MCTS-SPW); basically as in [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF] (for a problem with no stochastic part), i.e. with a bandit modified as in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF]. The second, third and fourth algorithms are three different versions of the MCTS with double progressive widening (MCTS-DPW [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF]); each one with a different value for the parameter β. The value of α was fixed to 0.4 throughout the experiment. This choice of α is traditional. As we will see in this paper, this is a reasonable choice.

As we can see in Fig. 2, MCTS-SPW performs quite poorly. Indeed, the support of the distribution of the inflows being continuous, the probability of drawing the same random event twice is null. Thus, this algorithm builds a tree of depth one, and never explores the upper levels except through Monte Carlo simulations. Doing so, it tends to evaluates decisions as if the policy used after these decisions was merely random walk. This is obviously not the right way to evaluate a decision. Indeed, if we make a decision at time step t, when reaching a new state, at time step t + 1, we will be given another time budget to make a new decision. This will be repeated until we reach the horizon. Hopefully, the decisions made from t + 1 to H will be better than the result of a pure blind search.

To account for this, we need to bias the evaluation of the new states, so that this evaluation simulates an intelligent agent, and not a random walk. This is exactly the aim of DPW.

The MTCS-DPW with β = 0.75 performs similarly to MCTS-SPW. This is due to the fact that the value of β leads MCTS to build a very wide tree, not tall enough. As MCTS-SPW, it explores the upper levels of the tree mostly through Monte Carlo simulations. Incidentally, this reduces the average number of simulations per node. The efficiency of MCTS relies on statistical information obtained through a large number of simulations. Hence, MCTS performances decrease with the average number of simulations per node. The MCTS-DPW with β = 0.4 and 0.25 perform much better than the two first algorithm, with the fastest convergence rate going to the version with β = 0.25. This is not a surprising result, given the setting of the problem. Since the random inflows are very small compared to the other parameters of the problem, it is of little importance to build a very wide tree at the random node level (i.e. to explore many different random occurrences of the events). In this setting, the best strategy is to explore very few random occurrences, and to build a tall tree, with many leaves being final nodes.

Experiments on a problem with high stochasticity

In this section, we add a discrete random event to the transition. We want this event to have a low probability of happening, but significantely impact the reward.

There are two main reasons for us to study this kind of problem. First, discriminate methods that see rare random events ahead in time and those that do not. Second, this kind of problem is often observed in real world data. In the models used by industrials for building energy policies, most assets (thermal plants, etc) have a low probability of failure. If these rare events are not taken into consideration, one may take unwise risks.

The discriminating power of the stock problem with thermal plant failure

To see how this can easily discriminate methods that misses rare events, let us consider the following modified stock problem. The stocks are tight, i.e. the total amount of energy that can be produced out of the stocks is lower than the expected demand. The decision maker is forced to use the thermal plant at least once to satisfy the demand. The thermal plant has now a probability of failure p at the last time step. With probability p, the demand at the last time step has to be satisfied with the stocks only; if not, the decision maker has to pay a significant failure cost.

In this situation, a method that does not see the possibility of a thermal plant failure will use the water stocks as much as possible, to lower the quadratic thermal production cost. More precisely, the thermal cost being quadratic, such a method will produce exactly the same amount of energy out of the thermal plant at each time step. Doing so, the decision maker will be left, at the last time step, with exactly the stock required to match the demand with the help of the thermal plant, expected to produce the same amount of energy as in the previous timestep. In the case where the failure does not happen, this greedy strategy returns the lowest possible cost. But, in the case of failure, the decision maker has not enough stock left, and pays the very high failure cost.

To effectively discriminate methods that does not see the rare event, we make sure that the expected cost of a failure is higher than the expected benefits of a greedy strategy.

In such a problem, a method that does see the possibility of a thermal plant failure will save some water to make sure that the decision maker has enough stock at the last time step to satisfy the demand without the thermal plant. The thermal cost being quadratic, in the case where the failure does not happen, this is more costly than the greedy stratefy. However, in the case where the failure does happen, the decision maker can satisfy the demand, without paying the failure costs.

Note that the practitionners problem is much more complicated and subtle than this one. They have to evaluate the cost of a failure (what is the cost of shutting down electricity in a certain region for a certain duration?), and to evaluate the probability for this event to happen. In this perspective, we want to inquire on how, by modifying the double progressive widening parameters, we can obtain different versions of MCTS. One may then choose a different set of parameters, according to the type of problem he/she is facing (low, or very low probability of failure, medium or high failure cost, etc).

Experiments with a low thermal failure probability

In this section, we consider the stock problem with thermal plant failure, with a short time horizon. We have 2 stocks, and a time horizon of 3. The initial stocks are of 100. The thermal plant can produce up to 50 at a cost 10 per square unit. The demand is time varying, but has an average value of 125. The failure cost is set to 100000 per missed units. The probability of failure is set to 0.1.

The parameter β being the one directly related to how we manage the exploration/eploitation dilemna at the random level, we first fix α to four different values, and study the impact of variations on β. Doing so, we observe that best results are obtained for α = 0.6, for any value of β. The results for α = 0.6 are shown in 3. We observe that the best value for β is 0.6, followed very closely by β = 0.8. On Fig. 4, we fixed β to 0.6, and plotted the performances of MCTS with different values of α. In this figure, we see that for a given value of β, the results obtained with different values of α can vary by a ratio of one to four. From these figures, we can conclude that: First, the best overall result is obtained with the version having α = β = 0.6. Second, a poor setting of α (e.g. to 0.2) makes the different versions of MCTS equivalent, all of them giving significantly worst results than the other settings of α. A wise tuning of α seems to be necessary before even trying to tune β.

In this section, we saw how the addition of a low probability/high impact event to the problem can dramatically change the values of the best set of parameters. More precisely, the best value for β went from 0.2 to 0.6. This shows that, the larger the impact of the random events is, the higher the value of β should be.

Experiments with a higher thermal failure probability

In this section, we change the probability of thermal plant failure. We set it to 0.5, making it a relatively high probable event. We keep the same failure cost, so that this event still has a very high impact of the overall reward. In this setting, the event of a failure is easier to spot. One intuition would be to guess that, in this case, one does not want to explore a lot of random occurrence, and focus on exploiting a few of them.

We ran the experiment, and it turned out to be wrong. We obtain similar results to the case with a low probability. The best setting for α remains around 0.6. The setting of α is still crucial, as is shown in Fig. 5. By plotting the results with α set to 0.6, we observe that the best values for β are 0.6 and 0.8. Note that the rewards are lower than in the previous section: this is due to the higher probability of thermal plant failure, that makes the problem much harder overall. These results indicates that, as long as a random event has a very high impact on the reward function, one wants to have a fine perception of it. To do so, one needs to use a sufficiently high value for the parameter β.

Conclusion

We obtained experimental evidence that, to solve even an easy stochastic stock management problem, MCTS-PW outperforms MCTS-SW, assuming a reasonable and easy to find set of parameters is used. We also saw that to solve a problem largely driven by its stochastic part (i.e. thermal plant failure), one needs to carefuly choose the second parameter of DPW (i.e. β). Our results indicate that a safe choice for β is between 0.4 and 0.6. Indeed, setting it to 0.8 gives very poor results in case of a low impact of the stochastic part, and setting it to 0.2 is inefficient on problems with high stochasticity. This choice gives a version of MCTS that performs well in both cases, with low and high stochasticity, independantly of the probability of the high impact events. One should keep in mind though, that the relative scale of the random events, compared to the deterministic part of the problem, does matter when chosing the parameter β.

Our study also confirmed that the first parameter of the progressive widening, α, is crucial to obtain reasonable performance. Our results indicates that one should set it to a value between 0.4 and 0.6.

As future work, we would like to develop a simple adaptative tuning of β, to make the algorithm robust to variations in the scale of the random events.

Fig. 1 .

 1 Fig. 1. MCTS algorithm phases.

Fig. 2 .

 2 Fig. 2. 2 stocks, 6 time steps, small inflows.

Fig. 3 .

 3 Fig. 3. 2 stocks, 3 time steps, α=0.6

Fig. 4 .

 4 Fig. 4. 2 stocks, 3 time steps, β=0.6

Fig. 5 .

 5 Fig. 5. 2 stocks, 3 time steps, α=0.6, p f ail = 0.5

Fig. 6 .

 6 Fig. 6. 2 stocks, 3 time steps, β=0.6, p f ail = 0.5

Acknowledgments

We thank Grid5000, that made our experiments possible (https://www.grid5000. fr/mediawiki/index.php/Grid5000:Home).


Adrien Couëtoux

Hassen Doghmen

Olivier Teytaud

Improving the exploration in Upper Confidence Trees

In the standard version of the UCT algorithm, in the case of a continuous set of decisions, the exploration of new decisions is done through blind search. This can lead to very inefficient exploration, particularly in the case of large dimension problems, which often happens in energy management problems, for instance. In an attempt to use the information gathered through past simulations to better explore new decisions, we propose a method named Blind Value (BV). It only requires the access to a function that randomly draws feasible decisions. We also implement it and compare it to the original version of continuous UCT. Our results show that it gives a significant increase in convergence speed, in dimensions 12 and 80.

Introduction and motivation

We consider a high dimensional continuous and stochastic sequential decision making problem. Both the decision space and state space are continuous. For the sake of simplicity, both have the same dimension N . There is a finite time horizon H, after which no further decisions are made. At each time step t < H, given a current state s t , the optimizer has to make a decision d. In this paper, we will denote the set of feasible decisions from state s as X(s). We will also denote the set of explored decisions from state s after the n th iteration, n ≥ 1, as D n (s).

We consider that the optimizer has at its disposal a model with a transition function f and a sampling function ϕ. The transition function takes as inputs a state s t and a decision x ∈ X(s t ). Its outputs are a state s t+1 and a reward r t+1 ∈ R. The sampling function takes as input a state s t , and its output is a decision x ∈ X(s t ). The optimizer has no other knowledge of the model than these two functions. Both functions can be (and are, in our experiments) stochastic: f (s t , d) and ϕ(s t ) are two multidimensional real random variables, their probability distributions being unknown to the optimizer.

The optimizer is given an initial state s 0 , and its objective is to maximize the accumulated reward 1≤i≤H r(i).

In this context, UCT like algorithms have been some of the most efficient methods, like MCTS in the game of Go [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF][START_REF] Chaslot | Progressive Strategies for Monte-Carlo Tree Search[END_REF][START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF][START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], or continuous MCTS on energy management problems [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF]. This is due, mostly, to the fact that without any dimension reduction technique (that is application specific), all other well known methods, like dynamic programming, fail [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Bertsekas | Neuro-dynamic Programming[END_REF].

However, in its current form, continuous MCTS does not use any information when it explores new decisions. This is not such a dramatic issue in discrete cases, or in low dimensional continuous cases, as one can just blindly cover most of the search space. But, in the case of a high dimensional continuous decision space, we think that the convergence speed could be greatly increased by biasing the way new decisions are explored. As mentioned before, we consider the case where the sampling of feasible decisions is "black box". This means that the set of feasible decision, as well as the inside of the sampling function ϕ, are unknown to the optimizer. This keeps biased sampling methods out of our options. We chose to consider this case because, to have access to the inside of the sampling function, one needs to know precisely the constraints of the model, and to implement them. Not only can this work take enourmous amounts of time (i.e.,hundreds of man hours), but the resulting feasible space may also be highly non convex, resulting in even more work to develop sampling functions on these spaces. In short, biased sampling, in our opinion, should be relevant for very problem-specific methods.

One could also count on an approximate knowledge of the feasible space, sample on this approximation, and apply a large penality to infeasible decisions. This is a valid option for many problems, but, in energy management problems (our main current application of interest), the feasible decisions are extremely sparse in the convex envelop, making this approach less interesting.

Our approach is focused on using the very limited information of the transition and sampling functions, in combination with the information progressively made available during the course of the simulations. This is inspired by a work on continuous and stochastic bandits problems [START_REF] Bubeck | Online optimization in x-armed bandits[END_REF], which provides a method that ensures that no area of the feasible decisions set is left unexplored, while focusing on promising areas of this set. However, it focuses on the theoretical aspect of the problem, and requires some assumptions that often do not hold in our case. In particular, it requires the knowledge of the set of feasible decisions. Still, our approach follows the same ideas: explore the empty areas first, and then to focus on areas where promising decisions are.

We first quickly review the state of the art form of MCTS in a continuous setting. Then, we introduce its new variant termed MCTS with Blind Value (MCTS-BV). Then, we show some experimental results on an energy management problem, where we compare the two versions, first in a small dimension setting, then in a larger dimension setting (N = 80). Finally, we present some experimental results on the tuning of one parameter of MCTS-BV.

State of the art of continuous Upper Confidence Trees

The UCT algorithm builds a tree where the nodes represent the reachable states, and the arcs the feasible decisions. By progressively adding arcs and nodes from its root (that represents the initial state given to the optimizer), more infor-mation is gathered. When the algorithm runs out of time, it selects the most promising decision reachable from the root (usually, the one that has been simulated the most). Among the crucial mechanisms in this algorithm, there are: when to add a new decision to the tree or when to exploit a known decision, and how to select a known decision once we have chosen not to add a new one. The first part is usually dealt with by using Progressive Widening [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF], while the second is usually dealt with by using an Upper Confidence Bound formula (UCB).

For more detailed information about the current state of the art form of MCTS with Double Progressive Widening (MCTS-DPW), please read [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF].

Blind Value

The principle of Blind Value is to help the exploration of new decisions. One can want to explore a new decision from any state already in the tree. Although in our case, the optimizer cannot bias the sampling of new decisions, we propose a method that does use the information available in the tree. More precisely, we use the information about the children of the current node. In terms of states and decisions, it means: when we want to explore a new decision from state s, we use information about all the decisions explored from this state s in the past simulations to select a new decision x ∈ X(s) to be explored from state s.

Note that one could use any other information in the tree: brother nodes, grand children nodes, father node, etc. However, even the exploitation of the direct children of a node only is computationally costly. And, the more distant in the tree some information is, the more likely it is to be irrelevant to the node we are currently in (states might be very different, and this type of problem is also highly time step dependant). [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] has proposed the use of Rapid Action Value Estimates (RAVE), which are an interesting other possibility; we will consider the mixing of blind value with RAVE values in a further work. [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] also proposed the use of information from related nodes; after preliminary positive results, this was later removed from the corresponding implementations (for the game of Go) for correctly tuned implementations.

The idea of BV is to try to explore decisions that are far away from known decisions during the first simulations, and then to focus on areas that have a lot of decisions with high UCB values. This is done by sampling a number of new decisions, and by selecting one of them according to a combination of these two criterions (explore unknown regions and explore regions with many decisions with high UCB values in it).

More precisely, we sample a number M ≥ 1 of random decisions, and we pick the one that is the most interesting to explore. The way we measure the interest of a decision is through a function from the decision space to R, denoted BV (.) (Blind Value). This function can be defined in many different ways. In this paper, at an iteration n, given a state s and a decision x ∈ X(s), we chose to define BV (x) as the minimum over D n (s) of the sum of two parts. The first part is the UCB value of d ∈ D n (s), the second is the distance between x ∈ X(s) and d ∈ D n (s), multiplied by an adaptation coefficient. We use the standard euclidian distance, but any other distance could be used instead.

More precisely, the Blind Value of x in state s with decisions d ∈ D n (s) already explored is

BV (x) = min

Experimental comparison

Our test case is an energy management problem. There are N energy stocks, H time steps, and a thermal power plant with a given maximum capacity and production cost function. In our experiments, we used a quadratic cost function. At each time step, each stock also receives an inflow. Each inflow follows its own independent random distribution.

At each time step, the decision maker has to decide how much to produce from each stock, and how much to produce from the thermal plant. His goal is to satisfy a time varying demand at the lowest possible cost.

We ran two algorithms on this problem: the continuous version of MCTS, as introduced in [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF], and the same algorithm with the addition of Blind Value (MCTS-BV), with the sample size parameter set to 20. This experiment was run with 12 stocks and 16 time steps. The results are shown in fig 1 (left). In this experiment, as in the following ones, each point is computed from 10000 runs of the algorithm on one problem instance. The 95% confidence intervals are plotted as blue segments around the points, even though their small size can make them very hard to see in some cases. This figure shows that even in dimension 12, BV already gives an edge of magnitude 10 to MCTS, in terms of computation time (to reach a certain level of performance, MCTS requires 10 times as many simulations as MCTS-BV). The problem being reasonably easy, we also see that this edge decreases when the computation time increases (but only for a computation time of about 3 minutes). This is due to the fact that, as the budget gets bigger, both algorithms get very close to the optimum, in terms of reward. This is why we made a second experiment, on the same problem, with a much higher dimension. In this experiment, there are 80 stocks, 6 time steps, and M = 640. With the information given to the algorithms (just the transition and the sampling functions), this problem is incredibly difficult, and naturally has very low reward (the highest average possible reward being around -2.5 × 10 7 ). Given its dimension, there is no way of exploring the entire decision space, even with a very low density. The results are shown in Fig. 1

-8e+06 -7e+06 -6e+06 -5e+06 -4e+06 -3e+06 -2e+06 -1e+06 -3 -2 -1 0 1 2 Reward log10(computation time) DPW+BV DPW -1.22e+10 -1.2e+10 -1.18e+10 -1.16e+10 -1.14e+10 1

(right).

This figure shows that BV still gives an edge of magnitude 10 to MCTS in terms of computation time, even though we were not able to approach the optimum with our computing capacities. One can also note that in this setting, the difference seems to be increasing as the budget increases. This leads to think that on very difficult problems, BV can divide by ten, or even more, the computing time necessary to reach a certain level of performance.

Conclusion and future work

We introduced a new variant of continuous MCTS to better solve high dimensional problems. Our experimental results show that this variant, MCTS-BV, improves the original algorithm by a factor 10 (it reaches the same level of performance with 10 times less simulations than the original). This result holds for even relatively small dimension problems (dimension 12). The edge given by BV seems to be even bigger in very high dimensions, but this could be confirmed by longer experiments.

We believe that, especially in its simplest form, Blind Value is very easy to implement, and can significantly increase the convergence speed of MCTS on continuous and stochastic planning problems.

It could also be coupled with other ways of exploiting information throughout the tree. One of the promising leads is the use of RAVE values, first introduced in the game of Go [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], and currently extended to continuous domains. While Blind Value only uses the decisions at the current level in the tree (horizontal propagation), RAVE propagates information through the path of each simulation, from child to father node (vertical propagation) enabling the algorithm to attribute a value to decisions not yet explored from one specific state.

Our future work will focus on setting an adaptive form for the sampling size parameter, to adapt it to the time budget. We also plan on trying different variants of the formula used to rank the decisions in the pool, by changing the distance, for example.

  d∈Dn(s) U CB(d) + ρdist(d, y). What follows is the detailed blind value algorithm: Exploration of new decisions Input: a state s, a set D of already explored decisions, an integer M , and a distance function over the decision space, dist Output: an unexplored decision x. Generate M random decisions. Let X be the set composed of these decisions. Compute a = U nbiasedStandardDeviation d∈D (U CB(d)) Compute b = U nbiasedStandardDeviationx∈X (dist(x, 0)), 0 being the center of the domain Compute ρ = a b return x = argmaxy∈X BV (y, ρ, D) Computing BV (Blind Value) Input: an unexplored decision y, a real number ρ, and D the set of explored decisions Output: a real number BV (y, ρ, D). return min d∈D (ρ × dist(d, y) + U CB(d))

  Left: reward, as a function of the computation time. Problem settings: 12 stocks, 16 time steps. MTCS with BV is 10 times faster than MCTS, for budgets up to 10 seconds per decision. Right: reward, as a function of the number of simulations per decision. Problem settings: 80 stocks, 6 time steps. MTCS with BV is 10 times faster than MCTS, for all budgets.

	DPW(0.5,0.6)
	DPW(0.5,0.6)+BV
	Reward
	1.5	2	2.5	3	3.5	4	4.5	5
			log10(number of simulations)
	Fig. 1.

Acknowledgments. We thank Grid5000, that made our experiments possible (www.grid5000.fr). We also thank the National Science Council of Taiwan for grants NSC97-2221-E-024-011-MY2 and NSC 99-2923-E-024-003-MY3.