Mathieu Santonja
email: mathieu.santonja@gmail.com

Adriane Aupic-Samain

Estelle Forey

Matthieu Chauvat

Increasing temperature and decreasing specific leaf area amplify centipede predation impact on Collembola

Keywords: climate change, Chilopoda, plant functional trait, predator-prey interaction, springtail

Collembola is an abundant group of soil organisms playing a major role on litter decomposition process and nutrient cycling in forest ecosystems. Habitat structure strongly influences Collembola assemblages as plant litter physical characteristics and quantity provide structural niches and determine the outcome of their interactions with predators. Collembola are also extremely sensitive to environmental conditions such as soil temperature that control their demographic parameters and activity. In this context, increasing temperature with the ongoing climate change can have strong impact on Collembola assemblages and their responses to predation either directly by altering their behaviour or indirectly by altering their habitat structure. We therefore examined how the increase of temperature combined to the decrease of specific leaf area (SLA, a major functional plant trait) of the European common oak (Quercus robur L.) and the presence of a centipede predator (Chilopoda: Lithobiidae) will affect the abundance of Folsomia candida (Collembola: Isotomidae) in a 5-week microcosm experiment.

Increasing temperature, decreasing SLA and presence of centipede altered F. candida abundance. We observed a significant temperature × predation interaction suggesting differential effects of increasing temperature on F. candida abundance with and without predator. We also observed a significant SLA × predation interaction highlighting that lower SLA decreases F. candida abundance only in predator presence. Finally, our findings evidenced that increasing temperature and decreasing SLA amplify the negative effect of centipede predation on F. candida abundance, suggesting that both direct and indirect effects of climate change would conjointly strengthen the top-down control of predators on preys.

Introduction

Soil biodiversity plays an essential role in ecosystem functioning, especially in biogeochemical cycles [START_REF] Bardgett | The biology of soil: a community and ecosystem approach[END_REF][START_REF] Hättenschwiler | Biodiversity and litter decomposition in terrestrial ecosystems[END_REF] with feedback on plant growth, ecosystem productivity and overall community structure [START_REF] Wardle | Linkages between plant litter decomposition, litter quality, and vegetation responses to herbivores[END_REF][START_REF] Gobat | Le sol vivant: bases de pédologie, biologie des sols[END_REF]. It has become increasingly clear during the last decades that soil biodiversity and related ecosystem services are extremely threatened by climate change [START_REF] Blankinship | A meta-analysis of responses of soil biota to global change[END_REF][START_REF] Montoya | Climate change, biotic interactions and ecosystem services[END_REF], through changes in species demographic parameters, species interactions [START_REF] Tylianakis | Global change and species interactions in terrestrial ecosystems[END_REF][START_REF] Van Der Putten | Predicting species distribution and abundance responses to climate change: why it is essential to include biotic interactions across trophic levels[END_REF], and eventually cascading effects on ecosystem processes [START_REF] Santonja | Plant litter mixture partly mitigates the negative effects of extended drought on soil biota and litter decomposition in a Mediterranean oak forest[END_REF][START_REF] Thakur | Reduced feeding activity of soil detritivores under warmer and drier conditions[END_REF]. As predator-prey interactions are a key structuring force in population dynamics [START_REF] Laws | Climate change effects on predator-prey interactions[END_REF][START_REF] Schmitz | Behaviour of predators and prey and links with population-level processes[END_REF], understanding the effects of climate change on these interactions is of primary importance to predict soil ecosystem responses.

Collembola, among the most widespread and abundant group of soil organisms [START_REF] Hopkin | Biology of Springtails (Insecta: Collembola)[END_REF], plays a major role in soil functioning [START_REF] Rusek | Biodiversity of Collembola and their functional role in the ecosystem[END_REF] by regulating the microbial (bacterial and fungal) communities, litter decomposition process and nutrient cycling, and consequently feedback on plants [START_REF] Cragg | How changes in soil faunal diversity and composition within a trophic group influence decomposition processes[END_REF][START_REF] Filser | The role of Collembola in carbon and nitrogen cycling in soil[END_REF][START_REF] Forey | Flowering phenology of a herbaceous species (Poa annua) is regulated by soil Collembola[END_REF][START_REF] Lawrence | Spider predation on forest-floor Collembola and evidence for indirect effects on decomposition[END_REF]. Collembola are also strongly top-down controlled by many predators including spiders [START_REF] Lawrence | Spider predation on forest-floor Collembola and evidence for indirect effects on decomposition[END_REF][START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF], centipedes [START_REF] Günther | Variations in prey consumption of centipede predators in forest soils as indicated by molecular gut content analysis[END_REF][START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF] or mites [START_REF] Thakur | Plant community composition determines the strength of topdown control in a soil food web motif[END_REF][START_REF] Thakur | Warming magnifies predation and reduces prey coexistence in a model litter arthropod system[END_REF]. Furthermore, Collembola are often under the influence of habitat structure as plant litter physical characteristics and quantity (i.e. litter thickness) provide niches serving as microhabitats for Collembola [START_REF] Santonja | Plant litter mixture partly mitigates the negative effects of extended drought on soil biota and litter decomposition in a Mediterranean oak forest[END_REF][START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF][START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF][START_REF] Sauvadet | Comparing the effects of litter quantity and quality on soil biota structure and functioning: application to a cultivated soil in Northern France[END_REF]. This habitat structure also acts as an important driver of prey-predator interactions by influencing encounter probabilities between Collembola and their predators [START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF][START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF].

As Collembola are also extremely sensitive to environmental conditions [START_REF] Hopkin | Biology of Springtails (Insecta: Collembola)[END_REF], increasing temperature and decreasing precipitation induced by ongoing climate change [START_REF] Bellard | Impacts of climate change on the future of biodiversity[END_REF][START_REF] Gilman | A framework for community interactions under climate change[END_REF][START_REF]Climate change 2014: impacts, adaptation, and vulnerability. Part A: global and sectoral aspects. Contribution of Working Group II to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF] can have strong direct impacts on Collembola demographic parameters (e.g. reproduction, development and survival) by altering both soil temperature and moisture conditions [START_REF] Kardol | Climate change effects on soil microarthropod abundance and community structure[END_REF][START_REF] Lindo | Warming favours small-bodied organisms through enhanced reproduction and compositional shifts in belowground systems[END_REF][START_REF] Xu | Seasonal exposure to drought and air warming affects soil Collembola and mites[END_REF]. As ectothermic organisms, Collembola and their predators generally exhibit greater activity with warming because of elevated metabolic demands [START_REF] Gillooly | Effects of size and temperature on metabolic rate[END_REF]. Several experimental field studies, simulating the impact of future climatic conditions in grassland and forest ecosystems, reported a decline in Collembola abundance and diversity in warmer and drier soil conditions, whereas they increased in warmer and wetter soils [START_REF] Santonja | Plant litter mixture partly mitigates the negative effects of extended drought on soil biota and litter decomposition in a Mediterranean oak forest[END_REF][START_REF] Xu | Seasonal exposure to drought and air warming affects soil Collembola and mites[END_REF][START_REF] Harte | Price Effects of manipulated soil microclimate on mesofaunal biomass and diversity[END_REF][START_REF] Lindberg | Effects of experimental irrigation and drought on the composition and diversity of soil fauna in a coniferous stand[END_REF][START_REF] Pflug | Influence of drought and litter age on Collembola communities[END_REF]. While there is a recent wealth of literature on warming effect on prey-predator interactions [START_REF] Gilman | A framework for community interactions under climate change[END_REF][START_REF] Abbott | The challenge of predicting temperature effects on short-term predator-prey dynamics[END_REF][START_REF] Amarasekare | Effects of temperature on consumer-resource interactions[END_REF][START_REF] Rall | Temperature, predatorprey interaction strength and population stability[END_REF], few attempts have been made on belowground organisms. For example Thakur et al. [START_REF] Thakur | Warming magnifies predation and reduces prey coexistence in a model litter arthropod system[END_REF] reported that predatory mites (Hypoaspis aculeifer and H. miles) reduced Collembola coexistence (Folsomia candida and Proisotoma minuta) with increasing temperature.

In addition, the ongoing climate change can also indirectly affect Collembola by altering litter physical characteristics and quantity produced by plants with thus cascading effects on both the food resource and microhabitat availability for Collembola as well as the outcome of their interactions with predators. In fact, climatic conditions strongly control leaf traits and consequently induce changes in litter traits [START_REF] Chen | Leaf nitrogen and phosphorus concentrations of woody plants differ in responses to climate, soil and plant growth form[END_REF][START_REF] Reich | Global patterns of plant leaf N and P in relation to temperature and latitude[END_REF][START_REF] Wright | Modulation of leaf economic traits and trait relationships by climate[END_REF]. Plants under warmer and drier climates tend to have thicker leaves (i.e. sclerophylly) and lower specific leaf area (SLA) in order to reduce water loss [START_REF] Wright | Modulation of leaf economic traits and trait relationships by climate[END_REF][START_REF] Pallardy | Physiology of woody plants[END_REF]. For example, Graça and Poquet [START_REF] Graça | Do climate and soil influence phenotypic variability in leaf litter, microbial decomposition and shredder consumption?[END_REF] reported that SLA of Quercus robur and Alnus glutinosa leaves decreased with increasing temperature across a wide European climatic gradient. As a consequence, for hemi-and epedaphic Collembola (i.e. living on the soil surface and in the leaf litter), this decrease in SLA could imply (i) a lower surface area for fungal colonization leading to a reduced fungal grazing, as well as (ii) less spatial refuges and higher probability to encounter their predators. However, to our knowledge, no previous study attempted to evaluate the consequences of a decrease in SLA on Collembola populations and their interactions with predators. Thus, our current understanding of soil organisms' responses to climate change drivers is still limited by a lack of studies addressing conjointly both direct and indirect effects of climate change on these organisms and their interactions. To address this gap, we designed a full factorial experiment in order to evaluate how the increase of atmospheric temperature (15 °C, 20 °C and 25 °C), the decrease of SLA (15.9 ± 0.5 vs. 11.7 ± 0.3 mm 2 .mg -1 ) of European oak leaves (Quercus robur L.) and the presence or absence of a centipede predator (Chilopoda: Lithobiidae) affect the abundance of Folsomia candida (Collembola: Isotomidae) in a 5-week microcosm experiment. The elevated temperature treatments were established in order to represent moderate (+5 °C) to high (+10 °C) climate warming scenarios [START_REF]Climate change 2014: impacts, adaptation, and vulnerability. Part A: global and sectoral aspects. Contribution of Working Group II to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change[END_REF], whereas the lowest temperature treatment was based on the climate at which F. candida was thermally acclimated (i.e. 15 °C). The decrease of SLA was established to simulate the impact of lower surface area for a same litter mass leading to an alteration of habitat structure. Previous to the experimentation, we carefully checked that the two oak litters (high and low SLA) only differed in their physical traits and not on their chemical traits (i.e. C:N ratio and phenolic concentration). We hypothesized that increasing temperature would induce higher predation effects on F. candida, as both prey and predator become more active and must encounter each other more frequently. We also hypothesized that decreased SLA would induce higher predation effects on F. candida, as a decrease in habitat complexity provides less spatial refuges for the prey population. Finally, the combination of both direct (i.e. temperature) and indirect (i.e. habitat structure) effects of climate change would conjointly strengthen the top-down control of predator on F. candida.

Materials and Methods

Material collection

Leaf litter

The experiment was conducted using leaf litter of a common and widespread deciduous tree in temperate European forest: the European oak (Quercus robur L.). Freshly-abscised shade leaves were collected on 5 individuals during the litter fall period (autumn 2016) in the Paimpont Forest (48°01'N, 2°10'W) and in the Rennes Forest (48°11'N, 1°34'W), northwestern France. In February 2017, 200 g of the leaf litter from both forests were enclosed in 0.5-mm mesh size litterbags and put on the litter layer under oak trees of the University of Rennes 1 campus (48°07'N, 1°38'W) in order to allow litter microbial colonization. Litter samples were collected after 2 months, dried at 40 °C for 48 h and frozen at -18 °C for 48 h in order to remove animals, and then stored in a dark room at ambient temperature until the start of the experiment.

Ten leaves were used to determine the specific leaf area (SLA) of Q. robur leaves for each forest. SLA was calculated as the ratio between leaf area and leaf dry weight and determined by weighing (± 0.01 mg) 3 leaf disks obtained with a cork borer (10 mm diameter) from the 10 randomly chosen leaves [START_REF] Graça | Do climate and soil influence phenotypic variability in leaf litter, microbial decomposition and shredder consumption?[END_REF]. The leaf dry weight was determined after drying leaf samples at 60 °C for 48 h. Oak leaves of Paimpont Forest showed a mean SLA of 15.9 ± 0.5 mm 2 .mg -1 (thereafter high SLA) while those of Rennes Forest showed a significant 26% lower SLA with a mean of 11.7 ± 0.3 mm 2 .mg -1 (thereafter low SLA) (t-test = 7.0, P < 0.001). In addition to SLA, C:N ratio and phenolic concentration of the two litter types were measured as these two plant functional traits were reported to also influence Collembola population dynamics [START_REF] Santonja | Plant litter mixture partly mitigates the negative effects of extended drought on soil biota and litter decomposition in a Mediterranean oak forest[END_REF][START_REF] Sauvadet | Comparing the effects of litter quantity and quality on soil biota structure and functioning: application to a cultivated soil in Northern France[END_REF][START_REF] Chomel | Secondary metabolites of Pinus halepensis alter decomposer organisms and litter decomposition during afforestation of abandoned agricultural zones[END_REF]. Carbon and N concentrations were determined by thermal combustion using a CN analyzer. Phenolic concentration was measured colorimetrically using the method described in Santonja et al. [START_REF] Santonja | Potential shift in plant communities with climate change in a Mediterranean Oak forest: consequence on nutrients and secondary metabolites release during litter decomposition[END_REF] with gallic acid as a standard. Leaf litter types of high and low SLA showed no significant difference in both C:N ratio (37.6 ± 0.6 vs. 40.6 ± 1.1, respectively; t-test = -2.3, P = 0.063) and phenolic concentration (49.3 ± 0.8 vs. 51.8 ± 0.9 mg.g -1 , respectively; t-test = -1.8, P = 0.123). As our research hypothesis was based on a physical effect of Quercus litter on predator-prey interaction (i.e. habitat structure) and not on a chemical effect of this litter (i.e. trophic or toxic role), we considered that we used two litter types exhibiting similar chemical properties but distinct physical properties to perform our experiment.

The experiment was conducted using two well-represented invertebrate groups from the leaf litter of European oak (Quercus robur L.) forests: Collembola as the prey and Chilopoda as the predator. Collembola used in this experiment was Folsomia candida (Collembola: Isotomidae), a parthenogenetic and ubiquitous hemiedaphic species known as fungivorous and frequently used in laboratory experiment [START_REF] Thakur | Warming magnifies predation and reduces prey coexistence in a model litter arthropod system[END_REF][START_REF] Fountain | Folsomia Candida (Collembola): a "standard" soil arthropod[END_REF]. Individuals were reared in plastic boxes (5.5 cm diameter × 7 cm height) containing a flat mixture of plaster of Paris and activated charcoal in a ratio 9:1, permanently water saturated. Individuals had been cultured at 15 °C and fed ad libitum with dry yeast pellets. To synchronize the age of the organisms, oviposition was stimulated by placing adults on a new breeding substrate [START_REF] Fountain | Folsomia Candida (Collembola): a "standard" soil arthropod[END_REF]. After oviposition, adults were removed and the eggs hatched 3-4 days later. To ensure that the population was as homogeneous as possible, eggs were placed in a large container and juveniles were fed for the first time altogether. We used 10-12 days juveniles of similar size (0.90 ± 0.08 mm; n = 10) that were starved 48 h before the start of the experiment.

Lithobiid centipedes (Chilopoda: Lithobiidae) were used as predator in this experiment.

They are known as active predators that live in the upper soil layers pursuing prey such as Collembola [START_REF] Hopkin | Biology of Springtails (Insecta: Collembola)[END_REF][START_REF] Coleman | Fundamentals of Soil Ecology[END_REF]. The centipedes were manually collected by sifting oak leaf litter of the Paimpont Forest. After collection, collected centipede individuals of similar size (10.81 ± 0.65 mm; n = 10) were kept separate from each other in moistened plastic boxes at 15 °C and were fed ad libitum with F. candida individuals. Centipede individuals were also starved 48 h before the start of the experiment.

Experimental setup

We tested the effects of three temperatures (15 °C, 20 °C, and 25 °C), two SLA (low vs. high) and centipede predation (no predator vs. predator presence) on Collembola abundance in a full factorial experiment. Each combination was replicated 7 times and then led to the construction of 84 microcosms, i.e. 3 temperatures × 2 SLA × 2 predation levels × 7 replicates.

Plastic boxes (12 cm diameter × 10 cm height covered by a nylon net to allow air circulation) were used as microcosms. Each microcosm was filled with 2 g (dry mass) oak leaf litter. In order to keep the base of microcosm moist, litter was added on top of a double layer of filter paper. In order to make the litter adequately moist and to stimulate microbial growth, 50 mg of yeast in 5 mL of deionized water were added on top of the litter 4 days before animals were added. Thirty individuals of F. candida were added into each of 84 microcosms at the start of the experiment. In order to allow prey acclimation to leaf litter habitat, one centipede individual was added 2 days after F. candida in each treatment including a predator (i.e. 42 microcosms).

The experiment was performed during 5 weeks in climate-controlled rooms (Percival AR-41L3) with a 12 h: 12 h light: dark photoperiod, a constant temperature (15 °C, 20 °C or 25 °C), and a constant 80% air humidity as centipedes are very sensitive to desiccation [START_REF] Jabin | Influence of environmental factors on the distribution pattern of centipedes (Chilopoda) and other soil arthropods in temperate deciduous forests[END_REF][START_REF] Lewis | The biology of centipedes[END_REF].

The microcosms were kept moist by adding 1 ml of deionized water every 2 days. The 15 °C treatment corresponded to the Collembola culture temperature, the 20 °C and 25 °C treatments to a +5 °C and +10 °C increase, respectively. The two SLA levels (15.9 ± 0.5 vs. 11.7 ± 0.3 mm 2 .mg -1 ) were used in order to simulate the impact of a reduction in leaf surface area (i.e. 31800 vs. 23400 mm 2 for 2 g of oak leaf litter) on Collembola fitness and Collembola-centipede interaction. At the end of the experiment, centipedes were removed by hand and leaf litter of each microcosm was placed on a Berlese-Tullgren funnel to collect Collembola. Individuals were harvested in 90% ethanol and then counted under a stereomicroscope.

Statistical analyses

Statistical analyses were performed using R software (version 3.4.2). A generalized linear model (GLM), followed by post-hoc multiple comparisons (Tukey contrasts), was used to test for the effect of temperature, SLA, centipede predation, and their interactions on Collembola abundance. We fitted the GLM model specifying a Poisson error distribution and log link function because the response variable was count data (i.e. number of Collembola per microcosm).

Results

Temperature, SLA and predation treatments had significant effects on Collembola abundance (Table 1, Fig. 1). On the whole experiment, we found that Collembola abundance was the highest at 20 °C and the lowest at 25 °C (Fig. 1a). For SLA, Collembola abundance was higher with high SLA than with low SLA (Fig. 1b). Lastly, predation treatment also altered Collembola abundance with higher Collembola abundance in absence of predator (Fig. 1c).

However, significant interactions between temperature and predation treatments, between SLA and predation treatments, and between the three treatments were observed (Table 1).

The interaction between temperature and predation treatments suggested that increasing temperature differentially affected Collembola abundance with or without a predator (Table 1, Fig. 2). Without predator, +5 °C favored Collembola abundance (+27% compared to 15 °C) whereas +10 °C negatively affected Collembola abundance (-18% compared to 15 °C). In presence of a predator, there was no difference in Collembola abundance between 15 °C and 20 °C, while Collembola abundance strongly decreased at 25°C (-55% compared to 15 °C). Furthermore, the negative effect of predation increased with increasing temperature, as the density of F. candida was reduced by 26%, 34%, and 59% at 15 °C, 20 °C and 25 °C, respectively.

The interaction between SLA and predation treatments suggested that the decrease of SLA negatively affected Collembola abundance only in predator presence (Table 1, Fig. 3). Furthermore, the negative effect of predation increased with the decrease of SLA, from a 28% reduction of Collembola abundance at high SLA to a 50% reduction at low SLA.

The interaction between temperature, SLA and predation treatments suggested that the combinations of specific temperature and SLA treatments conjointly alter the predator control of Collembola abundance (Table 1). In fact, the greatest top-down control was observed at 20 °C on low SLA (i.e. 70% reduction of Collembola abundance, Table 2), while the lowest topdown control was observed at 15 °C on high SLA (i.e. 18% reduction of Collembola abundance, Table 2).

Discussion

As expected, Collembola abundance was depressed by the presence of a centipede. This result is in accordance with previous studies, which reported that centipedes have strong negative effects on Collembola abundance [START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF][START_REF] Ferlian | Trophic interactions in centipedes (Chilopoda, Myriapoda) as indicated by fatty acid patterns: variations with life stage, forest age and season[END_REF][START_REF] Salmon | Earthworms and collembola relationships: effects of predatory centipedes and humus forms[END_REF]. In agreement with our first hypothesis, we demonstrated that predation effects became stronger with increasing temperature, from -26% at 15 °C to -59% at 25 °C. Grgic and Kos [START_REF] Grgic | Temperature preference in some centipede species of the genus Lithobius Leach, 1814 (Chilopoda: Lithobiidae)[END_REF] reported optimal temperatures for some European Lithobiidae species between 12 °C and 22 °C, while Chitty [START_REF] Chitty | Myriapods (centipedes and millipedes)[END_REF] reported this temperature range for temperate centipede species between 20 °C and 25 °C, suggesting that the centipedes during our experiment were active foragers. As ectothermic organisms, by increasing their activities with increasing temperature because of elevated metabolic demands [START_REF] Gillooly | Effects of size and temperature on metabolic rate[END_REF], higher encounter probabilities between Collembola and centipede induced this short-term increase of predation effects. Our result supports the recent findings of Thakur et al. [START_REF] Thakur | Reduced feeding activity of soil detritivores under warmer and drier conditions[END_REF] that also highlighted higher predation effects upon Collembola with increasing temperature. Interestingly, we also found an increase in Collembola abundance with +5 °C increase in temperature that could compensate for the predation impact, as we did not observe a difference in Collembola abundances between the treatments at 15 °C and 20 °C in centipede presence (Fig. 2). Our observation of a maximum abundance of F. candida at 20 °C is consistent with the general sigmoid curve obtained when considering the response of an organism over the whole temperature range where development may occur [START_REF] Wagner | Modeling insect development rates: a literature review and application of a biophysical model[END_REF]. Stam et al. [START_REF] Stam | Trade-offs in the life history and energy budget of the parthenogenetic collembolan Folsomia candida (Willem)[END_REF] reported a decrease in clutch size (number of eggs) of F. candida at temperature exceeding 22 °C compared with temperature around 15 °C. Fountain and Hopkin [START_REF] Fountain | Folsomia Candida (Collembola): a "standard" soil arthropod[END_REF] also reported an optimal temperature for hatching success at 21°C for F. candida. However, Collembola abundance was strongly reduced with +10 °C, and this direct negative effect, coupled with centipede presence, induced a strong decline of F. candida population.

In agreement with our second hypothesis, we also demonstrated that decreasing specific leaf area (SLA) induced higher predation effects on a Collembola population. In line with our findings, two previous short-term experiments at low temperatures revealed the importance of habitat structure for the per capita interaction strengths of generalist predators on their Collembola prey [START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF][START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF]. In a 24 h experiment at 18 °C day: 16 °C night regime, Vucic-Pestic et al. [START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF] showed a decrease in consumption rate by a spider (Pardosa lugubris) on its Collembola prey (Heteromurus nitidus) in presence of moss (Polytrichum formosum), highlighting the importance of refuge presence for the prey. In a 24 h experiment at 15 °C, Kalinkat et al. [START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF] reported a decrease in consumption rate of a predator centipede (Lithobius mutabilis) on its Collembola prey (H. nitidus) according to the increase of litter quantity (Fagus sylvatica), highlighting the importance of habitat size in the encounter probability between a predator and its prey. Kalinkat et al. [START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF] demonstrated thus that increasing litter quantity reduced the encounter rates by diluting the prey population to lower density. In the present study, in addition to the importance of i) litter presence [START_REF] Vucic-Pestic | Habitat structure and prey aggregation determine the functional response in a soil predator-prey interaction[END_REF] and ii) litter quantity [START_REF] Kalinkat | Habitat structure alters top-down control in litter communities[END_REF], we demonstrated for the first time the key importance of a leaf morphological trait as a regulating factor of predator-prey interactions in a leaf litter system. In consequence, the litter habitat modifications mediated by decreasing both litter quantity production [START_REF] Rodriguez-Ramirez | Shrub species richness decreases negative impacts of drought in a Mediterranean ecosystem[END_REF] and leaf litter SLA [START_REF] Graça | Do climate and soil influence phenotypic variability in leaf litter, microbial decomposition and shredder consumption?[END_REF] in response to climate change would conjointly amplify the predatory control of Collembola populations by decreasing refuge availability and increasing the encounter rate with their predators.

Finally, we also confirmed our last expectation that both increasing temperature and decreasing SLA conjointly strengthen the top-down control of a centipede predator on a F. candida population. In fact, the highest top-down effect was observed at the highest temperature coupled with the lowest SLA. A strong decrease of Collembola abundance could, in turn, leads to a negative impact on their predator population with profound repercussions on soil food web structure. Additionally, these soil cascading trophic effects might have consequences for feedback on plants, as the presence and identity of Collembola can influence nutrient availability for plants, plant traits and strategy, with consequences on both plant productivity and reproduction [START_REF] Santonja | Plant litter mixture partly mitigates the negative effects of extended drought on soil biota and litter decomposition in a Mediterranean oak forest[END_REF][START_REF] Filser | The role of Collembola in carbon and nitrogen cycling in soil[END_REF][START_REF] Forey | Flowering phenology of a herbaceous species (Poa annua) is regulated by soil Collembola[END_REF][START_REF] Lawrence | Spider predation on forest-floor Collembola and evidence for indirect effects on decomposition[END_REF]. As species interactions provide the mechanistic link between warming and ecosystem functions [START_REF] Laws | Climate change effects on predator-prey interactions[END_REF][START_REF] Hughes | Biological consequences of global warming: is the signal already apparent?[END_REF], our study suggests that predicting the consequences of climate change may be far from trivial and needs to take into account both direct and indirect effects of climate change to better understand the outcome of short-term dynamics of predatorprey interactions. Table 1. Output of the general linear model testing for the effects of temperature (15°C, 20°C and 25°C), SLA (low vs. high), predation (no predator vs. predator presence), and their interactions on Collembola abundance. d.f. = degrees of freedom. Chi-squared (χ²) and Different letters denote significant differences among treatments with a < b < c.

Tables

FiguresFig. 1 .

 1 Figures

Fig. 2 .Fig. 3 .

 23 Fig. 2. Collembola abundance according to the Temperature × Predation interaction. Each bar

Acknowledgement

We thank Anaïs Rancon and Kevin Hoeffner for their assistance during material collection, Cécile Sulmon-Maisonneuve and Christophe Piscart for their assistance during the laboratory experiment, and Pierre Mariotte for his reviewing of the English. We also thank the Experimental Ecology (ECOLEX) platform of the ECOBIO research unit for providing experimental infrastructures. Table 2. Collembola abundance (mean ± SE; n = 7) according to temperature (15°C, 20°C and 25°C), SLA (low vs. high), and centipede predation (no predator vs. predator presence) treatments. Temperature SLA No predator Predator


Nicolas Carrara
email: nicolas.carrara@orange.com

Romain Laroche
email: romain.laroche@microsoft.com

Jean-Léon Bouraoui
email: jeanleon.bouraoui@orange.com

Tanguy Urvoy
email: tanguy.urvoy@orange.com

Olivier Pietquin
email: olivier.pietquin@univ-lille1.fr

A Fitted-Q Algorithm for Budgeted MDPs

Keywords: Reinforcement Learning, Budgeted-MDP, Fitted-Q

We address the problem of budgeted reinforcement learning, in continuous state-space, using a batch of transitions. To this extend, we introduce a novel algorithm called Budgeted Fitted-Q (BFTQ). Benchmarks show that BFTQ performs as well as a regular Fitted-Q algorithm in a continuous 2-D world but also allows one to choose the right amount of budget that fits to a given task without the need of engineering the rewards. We believe that the general principles used to design BFTQ can be applied to extend others classical reinforcement learning algorithms for budgeted oriented applications.

Introduction

Classic reinforcement learning (RL) algorithms focus on the maximization of a unique expected reward signal. But many applications have multiple, possibly conflicting, objectives. For example, an autonomous driving car must both optimize its travel time, its fuel consumption, and the safety of people. In this example, the first two objectives are of the same nature: although conflicting on short term, they become coherent on the long term: if the fuel tank is depleted the travel time will be potentially infinite. In practice, by replacing this infinite value by the time needed to walk to the next fuel station, one gets a reasonable way to combine these two objectives into a single one. The safety objective is of different nature because: one cannot afford to work "on expectation"; It is quite difficult to assess the cost of a dramatic car accident and it's often more intuitive to think in term of probability for a given run to fail the constraints. The car should optimize the expected travel time while guaranteeing a crash probability strictly lower than the one of a human driver. In this case, methods using worst percentile scenario criteria like conditional value-at-risk (CVaR) [START_REF] Chow | Riskconstrained reinforcement learning with percentile risk criteria[END_REF]) may help to design a good strategy.

One can also consider a scenario where a military send drones to a survey mission, and can only afford to lose a known limited percentage. In such scenario, it is difficult to shape the drone casualties/cost in term of negative rewards but there is no need to deploy the whole CVaR machinery. The aim of our work is to handle a relaxation of the risk-sensitive RL problem where we want to maximize the expected primary reward while keeping a secondary criterion -on expectation -under a given budget. We formalize this problem as a Budgeted Markov Decision Process (BDMP) in continuous state-space [START_REF] Boutilier | Budget allocation using weakly coupled, constrained markov decision processes[END_REF]). Solving a BMDP is a harder problem than solving a Constrained Markov Decision Process (CDMP) [START_REF] Altman | Constrained Markov Decision Processes[END_REF] as it requires the budget to be a parameter of the policy.

We introduce Budgeted Fitted-Q (BFTQ), a practical extension of the Fitted-Q (FTQ) algorithm for BMDP. It takes as input a batch of RL transitions and estimates the optimal parametric strategies under budget. We experiment BFTQ on 2-D world with holes and we show that BFTQ performs as well as FTQ and that the obtained policy is not shaped for a specific budget.

Background and Related Works

Markov Decision Process

A Markov Decision Process (MDP) is formalized as a tuple S, A, R, P, γ r ; where S is the state set, A is the action set, R : S × A × S → R the (potentially stochastic) reward function, P : S × A × S → [0, 1] is the transition function, and γ r is the reward discount factor. The behaviour of the agent is defined as a (stochastic) policy π : S × A → [0, 1] 1 . Solving an MDP consists in finding a policy π * that maximises the γ r -discounted expected return

E π * [ t γ t r R(s t , a t , s t+1 )].
The optimal policy π * satisfies Bellman's optimality equation [START_REF] Bellman | Dynamic programming and lagrange multipliers[END_REF]

): π * (s) = argmax a∈A Q * (s, a) where Q * (s, a) = E s |s,a [R (s, a, s ) + γ r Q * (s , π * (s ))].
Fitted-Q (FTQ, [START_REF] Ernst | Tree-Based Batch Mode Reinforcement Learning[END_REF]) is a generic algorithm to solve MDPs with continuous state-space and unknown R and P . It implements Value-Iteration (V.I, [START_REF] Bellman | Dynamic programming and lagrange multipliers[END_REF]) with a regression model as a proxy for the Q-function. It uses a batch of transitions (s i , a i , r i , s i ) i∈[0,N ] which covers most of the state space. It trains the Q-function at each iteration of VI using a supervised learning algorithm that regresses the following supervised training batch:

{(s i , a i ), r i + γ r * max a Q(s i , a )} i∈[0,N ] .

Budgeted Markov Decision Processes

A Constrained Markov Decision Process (CMDP, [START_REF] Beutler | Optimal policies for controlled markov chains with a constraint[END_REF]; [START_REF] Altman | Constrained Markov Decision Processes[END_REF]) is an MDP augmented with a cost function C : S×A×S → R, a cost discount γ c , and a budget β. The cost function and its budget represent the "hard" constraint of the problem, while the reward function represents the task to complete. The problem of constrained RL consists in finding the policy which maximizes the expected return while keeping the discounted sum of the cost under the given budget β.

Formally π * = argmax π E π t γ t r R t s.t. E π t γ t c C t ≤ β (1)
where R t = R(s t , a t , s t+1 ) and C t = C(s t , a t , s t+1 ).The Budgeted Markov Decision Process (BMDP, [START_REF] Boutilier | Budget allocation using weakly coupled, constrained markov decision processes[END_REF]) problem is a generalisation of the CMDP problem where the objective is to find a generic policy π * β which works for any CMDP of budget β > 0. A convenient property of MDPs, is that the optimal policy is unique, deterministic, and greedy: π * (s) = argmax a Q(s, a). In a CMDP, and a fortiori in a BMDP, this is in general not the case. It has been shown indeed that the optimal policy under constraint is a random mixture of two deterministic policies (Beutler and Ross (1985, Theorem 4.4)). To illustrate this fact, let us consider the trivial BMDP on the left of Fig. 1. On this example we have E π R = 10π 1 and E π C = π 1 . The deterministic policy consisting in picking always the safe action is feasible for any β ≥ 0, but if β = 1/2, the most rewarding feasible policy is to pick randomly the safe and risky actions with equal probabilities. If we attempt to cast this BMDP into an MDP by replacing the costs by negative rewards, the policy we will obtain will be deterministic, hence suboptimal.

Related work

Figure 1: On the left hand side, a simple risky-vs-safe BMDP. The probability of picking the risky action is π 1 . On the right hand side an attempt to relax the problem with negative rewards.

Researchers got interested in resolving constrained sequential problems [START_REF] García | A Comprehensive Survey on Safe Reinforcement Learning[END_REF]), such as MDP under constraints [START_REF] Beutler | Optimal policies for controlled markov chains with a constraint[END_REF]; [START_REF] Altman | Constrained Markov Decision Processes[END_REF]). Undurti et al. ( 2010) proposes an algorithm to solve CMDP with a continuous state-space using the same principles as Fitted-Value-Iteration but it assumes that the environment (R, C and P ) is known. [START_REF] Geibel | Risk-sensitive reinforcement learning applied to control under constraints[END_REF]; [START_REF] Chow | Riskconstrained reinforcement learning with percentile risk criteria[END_REF]; [START_REF] Achiam | Constrained policy optimization[END_REF] propose algorithms for CMDP, but they require interactions with the environment during training (actor-critic, Q-learning and Policy Gradient, Constrainted-Policy-Optimization). [START_REF] Abe | Optimizing debt collections using constrained reinforcement learning[END_REF] work with constraint-batch RL but their solution is a Q-learning algorithm adapted to batch learning, which is known not to be a sample-efficient batch RL algorithm. Thomas et al. (2015); [START_REF] Petrik | Safe policy improvement by minimizing robust baseline regret[END_REF]; [START_REF] Laroche | Safe Policy Improvement with Baseline Bootstrapping[END_REF] introduced batch RL algorithms for risk sensitive problems but these algorithms were not adapted for continuous environments. Finally, one of the main drawback of most of all these algorithms is the fact that they resolve CMDP and not BMDP. The approaches relying on using Lagrangian/KKT conditions would fall under the same limitation. On the contrary, [START_REF] Boutilier | Budget allocation using weakly coupled, constrained markov decision processes[END_REF] resolve a BMDP using a VI-like algorithm. However it only applies to finite and known environments. The next section introduce the contribution of the paper: Budgeted Fitted-Q. In this section, we introduce Budgeted-Fitted-Q (BFTQ), a batch RL under constraints algorithm for BMDP, as an extension of the regular FTQ algorithm.

Budgeted Fitted-Q Iteration

Intuition

We illustrate the principle of BFTQ with a simple BMDP described on Fig. 2. On this example, the transition, reward, and constraint functions are fully deterministic and finite, and the state and action sets are of respective sizes 7 and 2. Starting from the initial state, the goal is to maximise the expected cumulative reward under constraint that the expected cumulative cost lays under β. There are only 3 parameters to optimise: π 0 = P(a 0 | start), π 1 = P(a 0 | s 2 ), and π 2 = P(a 0 | s 2 ). On the left hand side of the figure, on state s 1 , the action a 0 leads to a better reward R = 10 > 9 and a lesser cost C = 2 < 3 than action a 1 : this action is dominant for any budget. On the right hand side state s 2 , we retrieve the same safe/unsafe trade-off as in Figure 1: the best policy has to be mixed between actions a 0 and a 1 .

Assuming γ r = γ c = 1, the optimization problem of Eq. 1 becomes:

max π 0 ,π 1 ,π 2 π 0 • [10π 1 + 9(1 -π 1 )] + (1 -π 0 ) • [1 + 5π 2 + 8(1 -π 2 )] s.t. π 0 • [3 + 2π 1 + 3(1 -π 1 )] + (1 -π 0 ) • [5 + π 2 + 6(1 -π 2 )] ≤ β
In this example, one can see that we may easily separate the constrained optimization problem into one independent sub-problem for each sub-tree2 . For that purpose, a variable substitution is operated as follows. Intuitively speaking, the agent optimises its budget distribution over all possible actions:

max π 0 ,β 0 ,β 1 π 0 Q π r (a 0 , β 0 ) + (1 -π 0 )Q π r (a 1 , β 1 ) s.t. π 0 Q π c (a 0 , β 0 ) + (1 -π 0 )Q π c (a 1 , β 1 ) ≤ β where    Q π r (a 0 , β 0 ) = max π 1 [10π 1 + 9(1 -π 1 )] s.t. 2π 1 + 3(1 -π 1 ) ≤ β 0 Q π r (a 1 , β 1 ) = max π 2 [1 + 5π 2 + 8(1 -π 2 )] s.t. π 2 + 6(1 -π 2 ) ≤ β 1 Q π c (a 0 , β 0 ) = 3 + β 0 and Q π c (a 1 , β 1 ) = 5 + β 1
This simplifies into:

max π 0 ,β 0 ,β 1 10π 0 + (1 -π 0 ) • (27 + 3β 1 )/5 s.t. π 0 (3 + β 0 ) + (1 -π 0 )(5 + β 1 ) ≤ β

Algorithm

While Fig. 2 illustrates the method on a simple BMDP, it can be extended to non-finite environments. If the number of states is very large or even infinite, one needs to use function approximations. In BFTQ, two functions have to be approximated. The regular Q-function estimates the discounted sum of rewards; it is denoted here by Q r , and is defined on a state-action-budget tuple. The constraint Q-function estimates the discounted sum of constraints, denoted here by Q c ; it is defined on a state-action-budget tuple as well. For both Q-functions, the budget variable contextualises with the remaining current budget when evaluating the function. In the intuition example, budget variables are β 0 and β 1 . In Fig. 2, the environment transitions, rewards and constraints were assumed to be known. In most situations, the model of the environment is unknown. FTQ, like many others RL algorithms, overcomes this problem by using agent's interactions with the environment through a trial and error process. Those interactions are collected as transitions (s i , a i , r i , s i ) i∈[0,N ] . Since BFTQ solves a BMDP, the transitions are extended to (s i , a i , r i , s i , c i ) i∈[0,N ] . Because of the budget dependence of the BFTQ functions, the transitions must be further extended with budget values precise enough to capture the budget variations of each trajectory. The new transitions are denoted as (s i , a i , r i , s i , c i , β i ) i∈[0,N ] 3 . With this method, we will be able to construct the optimal policy for any input couple (s, β) corresponding to the current state and budget remaining. The following notations are used: n is the current iteration of BFTQ, i the index of the i th transition, f (x i ) reg ← --y i is the regression of f using database {(x i , y i )} i∈[1,N ] and ∆ A is the probability simplex over A .

BFTQ relies on two policies. The behavioural-policy π(s, a, β) : S × R → ∆ A is the classical stochastic policy mapping states to distributions over actions, augmented with the budget dependency. The budget-policy b(s, a, β) : S × A × R → R allocates constraint budget to each triplet (action, state, budget). BFTQ algorithm consists in iterating over its two Q-functions: the reward action-value Q-function Q n r is evaluated with Eq. 2, and the constraint action-value Q-function Q n c is evaluated with Eq. 3. Both may be trained with any supervised learning regression algorithm.

Q n+1 r (s i , a i , β i ) reg ← --r i + γ r a ∈A π n (s i , a , β i )Q n r (s i , a , b n (s i , a , β i )) (2) Q n+1 c (s i , a i , β i ) reg ← --c i + γ c a ∈A π n (s i , a , β i )Q n c (s i , a , b n (s i , a , β i )) (3) Ψ n =    π ∈ ∆ S×R A , b ∈ R S×A×R such that, ∀s ∈ S, ∀β ∈ R, a∈A π(s, a, β)Q n c (s, a, b(s, a, β)) ≤ β    (4) (π n+1 ,b n+1 ) ← argmax (π,b)∈Ψ n+1 a∈A π(s, a, β)Q n+1 r (s, a, b(s, a, β)) (5)
Similarly to regular FTQ, BFTQ updates iteratively its greedy policy (π n , b n ). Since taking some actions could exceed the budget, both budget-policy and behavioural-policy are jointly optimised under the constraint of belonging to set Ψ, described in Eq. 4, which denotes the search space for admissible (behavioural-policy, budget-policy) couples. Eq. 5 denotes the optimisation process. The optimisation described in Eq. 5 does not need to be explicitly computed, it can be performed as required. In the BFTQ algorithm, one does only need to compute Eq. 5 for the transitions in the learning base. A complete method to solve of Eq. 5 is described in Appendix A and B. The stop criterion of BFTQ is classically defined as a threshold η on Q-functions's parameters differences.

Policy Execution

The way an agent must use the resulting behavioural-policy π and budget-policy b over a trajectory is formalised in Eq. 6 and 7. Let β 0 be any initial budget and s 0 be any initial state. At each time step, the agent determines the distribution over the actions and the budget repartition. Then, it samples an action according to the distribution and replaces its current budget according to the budget repartition and the action sampled.

In the next section, we evaluate BFTQ on a set of randomly generated 2-D worlds.

Experiments

3. For example, if the maximum cumulative constraint of a problem is 1, then a basic way to create those transitions is to duplicate each transition of (si, ai, r i , s i , c i ) i∈[0,N ] with all β in the set {β : ∃n ∈ N such that β = 0.1n and β ∈ [0, 1]}.

a t ∼ π(s t , •, β t ) ( 6)

β t+1 = b(s t , a t , β t ) (7) s t+1 ∼ P (s t , a t , •) r t+1 ∼ R(s t , a t , s t+1 ) c t+1 ∼ C(s t , a t , s t+1 )
We carry out experiments on randomly generated continuous 10 × 10 2-D worlds. The agent starts in top-left corner (0, 0). The goal is to reach the bottom-right corner, at coordinates (9, 9), which ends the episode with an immediate reward of 1.

On its way to the goal, the agent may fall into randomly placed holes. In that case, it also ends the episode with a constraint of magnitude 1. There are three available actions: move right, move bottom and dont move. The two first actions yield stochastic transitions: a Gaussian noise of mean 0 and standard deviation σ = 0.5 is applied on the direction followed. In the following experiments, we use two different RL agents. The first one, BFTQ(β) uses BFTQ algorithm to learn its policy. Q r , Q c , π and b are approximated with regression trees. The algorithm used for computing the convex hull is the Graham scan [START_REF] Graham | An efficient algorithm for determining the convex hull of a finite planar set[END_REF], details are left in Appendix B). β is the budget used when initiating a new trajectory. Note that all BFTQ(β) agents use Eq. 2 and 3. The second agent: FTQ(λ) uses FTQ with a regression tree. λ is used when penalizing a fall into a hole: r ← r-λc. We evaluate BFTQ(β) on 30 randomly generated 10 × 10 continuous 2-D worlds. In each grid world, 25% of the cells are randomly elected as holes. The training dataset is uniformly distributed over the state-action sets (30 transitions of 3 actions in 400 states -each step of value 0.5 -). The trained policy is evaluated on a total of 10 4 trajectories.

Since holes are constraints of value 1 and are absorbing, the constraints can be seen as failing probability. The same goes for rewards as success probability. In consequence, we test the policies for each budget β -or maximal failing probability -from 0 to 1. Results are shown in Fig. 3. From 0.0 to 0.67, budgets are not exceeded. Actually, the budget is even almost completely spent. This behaviour is typical of under constraint optimisation where optimal solutions are really close to the constraints. The reward also increases accordingly, but from β = 0.67 to β = 1.0, failing probability is capped as well as the reward. The explication is the following: at some point, the agent had to take some risk to get the reward; but taking more risk won't necessary give it more reward, because the path to the reward is not that risky. We can also observe the phenomena where either FTQ computes a super safe policy for λ ∈ {100, 10 4 } either it computes a really risky policy when λ ∈ {10, 1}. It seems impossible to find the right λ in order to stay bellow a budget of value 0.3 for example. On the other hand, the BFTQ agent is free to choose any budget value it wants to respect without worrying about the reward design.

On Fig 3, BFTQ reaches the same amount of reward return as FTQ. One can even note that, in this experiment, BFTQ is better than FTQ when budget is unlimited and /λ is low. In theory, reward returns should be similar. We believe that some generalization errors occurs for FTQ while BFTQ is more robust to themin this particular context. The impact of the generalization and the approximate method used to solve Eq 5 will be analysed in further work .But if one focus on the BFTQ algorithm, assumes regression algorithms used are perfect and optimisation method find the optimal solution of the non linear program in Eq 5, then BFTQ fits the requirement of the BMDP task.

Conclusion

In this paper we introduce BFTQ, a direct extension of FTQ to solve BMDP problem. We test the algorithm on 2-D world and we show that BFTQ performs as well as FTQ in terms of reward/constraint raised couple but also enables to carefully choose the amount of budget the agent can spend.

We believe that classic single reward oriented reinforcement learning algorithms can be extended to solve BMDP in the same way. It may also be of interest to find a close form solution for the program in Eq 5, which would speed up considerably the computation time of BFTQ.

c (s, a ⊥ , b ⊥ ) and Q c (s, a , b ). The value y β is then equal to π(s, a ⊥ , β)Q r (s, a ⊥ , β) + π(s, a , β)Q r (s, a , β). π(s, a , β) + π(s, a , β) = 1, if β ≤ Q c (s, a ⊥ , b ⊥ ), π(s, a , β) = 0, ( 10
) if β ≥ Q c (s, a , b ), π(s, a , β) = 1, otherwise, π(s, a , β) = β -Q c (s, a ⊥ , b ⊥ ) Q c (s, a , b ) -Q c (s, a ⊥ , b ⊥ ) . b(s, a ⊥ , β) = b ⊥ (11) b(s, a , β) = b (12)
One can extend this reasoning to cases with more than two actions by considering actions two by two. Finally solving Eq 9 actually amounts to solve the following program: For β = 0.2, the agent tries to reach the goal with more insistence but still stops some trajectories prematurely. Finally, for β = 0.3, the agent does not stop until it reaches the goal.

π n+1 (s i , •, β i ),b n+1 (s i , •, β i ) reg ← --argmax (π i ,b i )∈Ω n+1 i a∈A π i (a)Q n+1 r (s i , a, b i (a)) (13)

Appendix C. Experiments

Figure 2 :

 2 Figure 2: A simple deterministic finite BMDP.

Figure 3 :

 3 Figure 3: BFTQ(β) and FTQ(λ) reward w.r.t the constraints. Values near the dots are the budgets β allowed for BFTQ and the value λ for FTQ. Each dot is the mean on 30 2-D worlds with 1000 test trajectories on each of them. The standard deviation plotted refer to the variability between the random 2-D worlds.

Figure 4 :

 4 Figure 4: An example of Q-functions. The dot lines are tangent to both curves. The tangent at the right defines the optimal policy when the budget β is defined between Q c (s, a ⊥ , b ⊥ ) and Q c (s, a , b ). The value y β is then equal to π(s, a ⊥ , β)Q r (s, a ⊥ , β) + π(s, a , β)Q r (s, a , β).

Figure 5 :

 5 Figure 5: An execution of SOLVE with three actions. Each dot corresponds to the discretization w.r.t β. Red dots are considered to compute the convex hull. Blue dots are removed since they reach a worst value of Q r for greater Q c . Finally, pink cross are the dots retained to compute the optimal policy.

Figure 6 :

 6 Figure 6: A 4 × 4 2D world.

Figure 7 :

 7 Figure7: Execution of a BFTQ policy. Test trajectories are in blue, constraints in red and rewards in green. For a low budget, 0.1, the agent stops its trajectory after 1 or 2 actions. For β = 0.2, the agent tries to reach the goal with more insistence but still stops some trajectories prematurely. Finally, for β = 0.3, the agent does not stop until it reaches the goal.

Fig 6

 6 Fig 6 describes an example of small 2-D world. Fig 7 describes the trajectories followed by a BFTQ policy for several budgets.

To the best of our knowledge, for general BMDP -with loops -this separability assumption is still a conjecture.

The so-called Graham Scan[START_REF] Graham | An efficient algorithm for determining the convex hull of a finite planar set[END_REF]) fits all those criteria.

Appendix A. Scalability of BFTQ

The downside of Eq. 5 is that one has to solve a non-linear problem under constraints each time both policies are called (Eq. 6, 7, 2 and 3). For Eq. 6 and 7, this process is online: it would be disastrous for time-critic applications. To overcome this issue, we propose to approximate π and b using regressions. For that, instead of Eq. 4, one needs to compute ψ i (Eq. 8), the set of admissible behavioural/budgets policies couple for a set of samples (s i , β i ) j∈N i . One may design those samples using transitions (s i , a i , r i , s i , c i , β i ) i∈[0,N ] but it's not a requirement.

Eq. 9 describes how the budget-policy and behavioural-policy are updated at each iteration of BFTQ.

Appendix B. Solving the non-linear problem

The main remaining challenge is solving the non-linear problem in Eq 9. One may use random sampling, SLSQP [START_REF] Kraft | Slsqp, a nonlinear programming method with quadratic programming subproblems[END_REF]) or some black box optimisation algorithm such as genetic algorithms to find the optimal budget and action policy for a given transition. But it would be inefficient, because it would disregard some properties of the Q-functions.

Let Q s,a (β) denote the following parametric function:

Q is concave and strictly increasing in β along the axis of Q r . Indeed, given a budget β, a state s and an action a, the expected reward and actual budget consumption for a given action, Q r (s, a, β) and Q c (s, a, β) will be lower or equals to the ones yield by a larger budget β = β + ∀ ≥ 0. The intuition is as follows: given a budget β , in worst case scenarios (when extra budget is useless), one can always achieve at least the same performances as with the lower budget β since the space of admissible policies for β contains the one for β.

We need to solve Eq 5 for a state s. For the moment, we assume to have 2 possible actions a ⊥ and a . The functions Q s,a ⊥ and Q s,a are plotted on Fig 4 . The optimal Q r value is necessarily obtained by the probabilist combination of those actions. This combination of actions yield values (Q c , Q r ) on a straight line. Since Q functions are concave and strictly increasing, the line defining the optimal and admissible solutions is actually the tangent of both Q s,a ⊥ and Q s,a , lying on top of both functions as shown on Fig 4. This line is unique and we need to find both intersections points between the tangent and the Q functions to define the optimal solution. Let

)) denote the two intersections points. Then, the optimal behavioural-policy in s is described in Eq 10 and optimal budget-policy in s is then defined in Eq 12.

where

One way to solve Eq 13 is to compute the convex hull of the discrete version of Q functions. We propose an algorithm named SOLVE in Alg 1 to do so and show an example of its execution in Fig 5 . We assume that the function hull returns the convex hull H of a set in clockwise order starting with the lowest value in Qc, the corresponding budgets B and the corresponding actions A P 4 . To operate a reasonable discretization of Q-function and reduce the search space, we also need to know the maximal budget the environment could consume, we call it β max . Finally, Alg. 2 recalls the complete BFTQ algorithm using Eq. 13. The algorithm should stop when b and pi don't change too much between two iterations. The distances may use parameters of π and b approximations. Note that, since each transition has been extended with several values of β, at each iteration, you can save extra computations by pre-computing the convex hulls for each state in the batch of transitions and re-use these hulls for each β.

Algorithm 1 SOLVE

In: s, Q r , Q c , N, β, β max Out: π, b P = ∅ for a in A do for i = 0 to N do step = i/N * β max p = (Q c (s, a, step), Q r (s, a, step)) P = P ∪ p end for end for H, B, A P = hull(P) f ound = T rue i = 0 while ¬ f ound do q c , q r = H


Nicolas Carrara

Romain Laroche

Jean-Léon Bouraoui

Tanguy Urvoy

Olivier Pietquin

Safe transfer learning for dialogue applications

Keywords: Transfer Learning, Dialogue, Safety

come   L'archive ouverte pluridisciplinaire

Introduction

During its early steps of learning, a Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] based dialogue agent does a lot of exploration that may lead to penalizing behavior. However, the first interactions between a user and a dialogue system are crucial to gain his trust. To improve jump-start performance of an RL agent, one can transfer a strategy [START_REF] Taylor | Transfer Learning for Reinforcement Learning Domains : A Survey[END_REF][START_REF] Lazaric | Transfer in Reinforcement Learning: a Framework and a Survey[END_REF]. In dialogue, the strategy focuses on the success of the dialogue while minimizing its length [START_REF] Casanueva | Knowledge transfer between speakers for personalised dialogue management[END_REF][START_REF] Genevay | Transfer learning for user adaptation in spoken dialogue systems[END_REF][START_REF] Carrara | Online learning and transfer for user adaptation in dialogue systems[END_REF][START_REF] Chandramohan | Optimizing Spoken Dialogue Management from Data Corpora with Fitted Value Iteration[END_REF]. Rushing the dialogue may be problematic with some users and induce premature dialogue hangups. In one hand, it could lead to the lose of this user once for all. In an other hand, the lack of succeeding dialogues may affect the learning speed of the RL agent. To this extend, we introduce a novel algorithm : -safe. It transfers a safe strategy which avoid any critical dialogue act to avoid the aforementioned problems.

-safe

-safe (Fig 1) is a Q-learning algorithm [START_REF] Watkins | Q-learning[END_REF] where each action is decided by a randomly chosen policy among the greedy policy, an exploratory policy and the transferred safe policy. It may be an handcrafted policy, an RL policy (with large reward penalty on the catastrophic event) or even a safe-RL policy [START_REF] Carrara | A Fitted-Q Algorithm for Budgeted MDPs[END_REF].

Fig. 1: -safe algorithm.

Experiment

We test our algorithm on a simple slot-filling application. The agent ask for slot values, slot by slot in a fix order. Several acts are available :

-ask_next : ask next slot (with NLU errors).

-repeat_oral : repeat current slot (with NLU errors).

-repeat_numpad: repeat using numeric pad (without NLU errors).

-summarize_inform: summarize slots values and return the form result. If values are correct, the dialogue ends successfully, if not, the slot values are reset and the dialogue continues from the first slot.

repeat_numpad is an unsafe action : the user hangups with probability p. For each new user, p is randomly generated. An histogram of p values is displayed We define 2 handcrafted dialogue systems. The safe system uses repeat_oral if the recognition score is bellow 0.5, otherwise ask_next, or summarize_inform after the last slot; The unsafe system uses repeat_numpad instead. We compare two -safe agents. safe_on uses safe as transferred policy while unsafe_on transfers the unsafe policy. We see that despite a slightly difference on the dialogue success, the dialogue score is the same. That means -safe doesn't improve the learning speed of the greedy policy even if it is conservative enough to keep the user in the dialogue by avoiding catastrophic acts.

Future work

We believe that the hangup-model is too simple, so we plan to design the hangupmodel with a Poisson distribution. We also want to replace the handcrafted policies by actual RL policies learned on source users. Finally, a real application on DSTC2 may be considered.

  Fig 2.

Fig. 2 :

 2 Fig. 2: Half-gaussian distribution of p values.

Fig. 3 :

 3 Fig. 3: Performance of the greedy policies.