Sushovan Dam

Jean-Marie Pagès
email: jean-marie.pages@univ-amu.fr

Muriel Masi

Stress responses, outer membrane permeability control and antimicrobial resistance in 1 Enterobacteriaceae 2 3

Keywords: Enterobacteriaceae, envelope stress responses, outer membrane permeability, 15 porins, drug translocation, multidrug resistance. 16 17

outer membrane (OM), inner membrane (IMI), peptidoglycan (PG), 22 lipopolysaccharide (LPS), antimicrobial resistance (AMR), multidrug resistance (MDR), 23 envelope stress response (ESR), two-component system (TCS), small regulatory RNA 24 (sRNA).

Introduction 41

Antimicrobial resistance (AMR) is broadly recognized as a growing threat for human health 42 [1,2,3]. As such, increasing antibiotic treatment failures due to multidrug resistant (MDR) [START_REF] Thompson | SigmaE regulates and is regulated by a 427 small RNA in Escherichia coli[END_REF] bacteria have stirred the urgent need to better understand the underlying molecular 44 mechanisms and promote innovation with the development of new antibiotics and alternative Antibiotic stresses [START_REF] Andersen | micF RNA binds to the 5' end of ompF mRNA and to a 508 protein from Escherichia coli[END_REF] Bacteria are present in a wide range of environments in which they are exposed to diverse 75 toxic compounds or growth-limiting conditions. These include antibiotics used in the medical 76 environment and agricultural settings. The last few decades have been marked by the constant 77 increase of (multi)drug resistant clinical isolates to which we responded by increasing 78 antibiotic dosing. Therefore, antibiotics are present almost everywhere at different 79 concentrations [START_REF] Andersson | Microbiological effects of sublethal levels of antibiotics[END_REF]. Although MDR still emerges from bacterial exposure to antibiotic 80 concentrations that are higher than the minimal inhibitory concentrations (MIC, defined as 81 the lowest concentration of a drug that inhibit bacterial growth in defined laboratory 82 conditions), the effects of subinhibitory concentrations on bacterial physiology and AMR was 83 mostly disregarded. Importantly, studies in this field have shown that low antibiotic 84 concentrations affect bacteria at least at four different levels: as selectors of resistance (by 85 enriching resistant bacteria within populations and selecting for de novo resistance mutations) 86 [START_REF] Gullberg | Selection of resistant 369 bacteria at very low antibiotic concentrations[END_REF]; (ii) as contributors of genetic and phenotypic heterogeneity [START_REF] Gutierrez | β-lactam 371 antibiotics promote bacterial mutagenesis via an RpoS-mediated reduction in replication 372 fidelity[END_REF]; (iii) as intercellular 87 signals [START_REF] Lee | Bacterial charity work leads to 374 population-wide resistance[END_REF]; (iv) as inducers of persistence [START_REF] Pu | Enhanced efflux activity facilitates drug 376 tolerance in dormant bacterial cells[END_REF]. In this regard, Viveiros and colleagues have 88 demonstrated the induction of high-level resistance to tetracycline (TET) in susceptible E. 89 coli K12 obtained by gradual, step-wise increase exposure to subinhibitory concentrations of 90 the antibiotic [START_REF] Viveiros | Inducement and 378 reversal of tetracycline resistance in Escherichia coli K-12 and expression of proton gradient-379 dependent multidrug efflux pump genes[END_REF]. Increased expression of the AcrAB efflux pump was found responsible for 91 resistance to TET, which could also be reversed by the use of the efflux pump inhibitor 92 phenylalanine-arginine-β-naphthylamide (PAβN). Interestingly, the TET-resistant strain also 93 exhibited MDR due to repression of OmpF and OmpC expression [START_REF] Viveiros | Antibiotic 381 stress, genetic response and altered permeability of E. coli[END_REF]. Important questions 94 arise from this and other related studies. First is whether the target for signaling resistance is 95 the same as the target that is inhibited by the antibiotic. In case the antibiotic itself but not a 96 secondary metabolite is the signaling molecule, this could be determined by examining 97 whether the response is alleviated by a target mutation that prevents drug binding. Second is 98 whether and how the antibiotic (or a secondary metabolite) interferes with the ESRs 99 described above. Here, comparative transcriptomics between susceptible and resistant strains 100 would be a valuable tool to answer this question. RamA (absent in E. coli) and Rob as well as the oxidative stress regulon SoxSR [START_REF] Bolla | Membrane 349 permeability and regulation of drug "influx and efflux" in enterobacterial pathogens[END_REF][START_REF] Cohen | MarA locus causes decreased expression of 383 OmpF porin in multiple-antibiotic-resistant (Mar) mutants of Escherichia coli[END_REF][START_REF] George | Multidrug resistance in Klebsiella pneumoniae: 386 a novel gene, ramA, confers a multidrug resistance phenotype in Escherichia coli[END_REF][START_REF] Chubiz | Role of the mar-sox-rob regulon in regulating outer membrane 389 porin expression[END_REF][START_REF] Chollet | mar operon involved 391 in multidrug resistance of Enterobacter aerogenes[END_REF][START_REF] Chollet | RamA is an alternate 394 activator of the multidrug resistance cascade in Enterobacter aerogenes[END_REF].

106

Mutations in the corresponding genes are well-documented and induce the overproduction of 107 efflux pumps with concomitant repression of porin expression both directly and indirectly 108 [START_REF] Bolla | Membrane 349 permeability and regulation of drug "influx and efflux" in enterobacterial pathogens[END_REF]. These mechanisms are reviewed in details in Davin et al. [START_REF] Bolla | Membrane 349 permeability and regulation of drug "influx and efflux" in enterobacterial pathogens[END_REF]. Negative regulation by 109 repressors of porins also plays a major role. OmpX is a small OM channel [START_REF] Dupont | Enterobacter aerogenes 397 OmpX, a cation-selective channel mar-and osmo-regulated[END_REF], of which 110 overexpression is associated with a decreased expression of Omp36 (the OmpC ortholog of 111 Enterobacter aerogenes) and a decreased susceptibility to β-lactams [START_REF] Gayet | Modification of outer 399 membrane protein profile and evidence suggesting an active drug pump in Enterobacter 400 aerogenes clinical strains[END_REF][START_REF] Dupont | An early response to environmental 402 stress involves regulation of OmpX and OmpF, two enterobacterial outer membrane pore-403 forming proteins[END_REF]. Studies have CpxAR (Cpx), BaeRS, and Rcs phosphorelays, the stress responsive alternative sigma factor 125 σ E , and the phage shock response [START_REF] Majdalani | The Rcs phosphorelay: a complex signal transduction 409 system[END_REF][START_REF] Ruiz | Sensing external stress: watchdogs of the Escherichia coli cell 411 envelope[END_REF][START_REF] Rowley | Pushing the envelope: 413 extracytoplasmic stress responses in bacterial pathogens[END_REF][START_REF] Raivio | Everything old is new again: an update on current research on the Cpx 415 envelope stress response[END_REF] in E. coli and closely related Enterobacteriaceae.

126

Each of these ESRs is activated following the perturbation of particular components of the 127 envelope or exposure to particular environmental stresses. Although ESRs are important for 128 reacting to damaging conditions, stress proteins also play important roles in the maintenance 129 of basic cellular physiology [START_REF] Hayden | The extracytoplasmic stress factor, sigmaE, is required to 417 maintain cell envelope integrity in Escherichia coli[END_REF][START_REF] Delhaye | Fine-Tuning of the Cpx envelope stress response is 419 required for cell wall homeostasis in Escherichia coli[END_REF]. This is particularly true for the σ E -dependent stress 130 response in E. coli, as the rpoE gene, which encodes σ E , is essential for viability [START_REF] Las Penas | SigmaE is an essential sigma factor in 421 Escherichia coli[END_REF]. Here, 131 we will essentially focus on ESRs that impact on AMR by regulating porin expression 132 together with many other targets (regulons) -namely EnvZ/OmpR, Cpx and σ E (see below 133 and key figure). Additionally, with the recent highlights and advances in RNA-based 134 techniques [START_REF] Wassarman | Global approaches for finding small RNA and small 423 open reading frame functions[END_REF], the repertoire of small regulatory RNAs (sRNAs) has vastly increased so as 135 to and their impact on the OM is continuously emerging [START_REF] Guillier | Modulating the outer membrane with small 361 RNAs[END_REF][START_REF] Valentin-Hansen | Small RNAs controlling outer 365 membrane porins[END_REF]. sRNAs alter gene 136 expression, allowing fast adjustment to different growth conditions [START_REF] Gottesman | The small RNA regulators of Escherichia coli: roles and mechanisms[END_REF]. Noteworthy, ESRs 137 are often interconnected, regulate and are regulated by sRNAs in order control target genes 138 both at the transcriptional and post-transcriptional levels [15-17, 43, 44] (see below and key 139 figure).

140

Osmolarity was one of the earliest stresses described to influence OmpF and OmpC 141 expression via the EnvZ/OmpR two-component system (TCS) [START_REF] Mizuno | Signal transduction and gene regulation through the 431 phosphorylation of two regulatory components: the molecular basis for the osmotic 432 regulation of the porin genes[END_REF][START_REF] Pratt | From acids to osmZ: multiple factors 434 influence synthesis of the OmpF and OmpC porins in Escherichia coli[END_REF]. EnvZ is a membrane-142 bound sensor kinase, and OmpR is a cytosolic response regulator, which binds to the 143 promoter region of the porin genes. Upon activation, EnvZ autophosphorylates and the high 144 energy phosphoryl group from EnvZ is subsequently transferred to a conserved Asp residue 145 on OmpR. Phosphorylated OmpR (OmpR~P) serves as a transcription factor that 146 differentially modulates the expression of the ompF and ompC porin genes [START_REF] Mizuno | Signal transduction and gene regulation through the 431 phosphorylation of two regulatory components: the molecular basis for the osmotic 432 regulation of the porin genes[END_REF]. At low 147 osmolarity, high levels of OmpR~P activates ompF transcription, whereas at high osmolarity, 148 low levels of OmpR~P represses ompF transcription and activates ompC transcription [START_REF] Cai | EnvZ-OmpR interaction and osmoregulation in Escherichia coli[END_REF].

149

This differential production of OmpF and OmpC is consistent with that in high osmolarity 150 environments, such as in the hosts where nutrients are abundant the least permeable pore 151 channel OmpC is predominant, thus limiting the uptake of toxic bile salts; whereas in low 152 osmolarity environments where nutrients are scarce, the most permeable pore channel OmpF 153 is expressed [START_REF] Nikaido | Molecular basis of bacterial outer membrane permeability revisited[END_REF]. OmpF and OmpC transcriptional regulation by EnvZ/OmpR is also triggered 154 by local anesthetics, pH, and nutrient limitation [START_REF] Pratt | From acids to osmZ: multiple factors 434 influence synthesis of the OmpF and OmpC porins in Escherichia coli[END_REF].

155

Accumulation of misfolded OM proteins in the periplasm, presumably reflecting problems in 156 protein assembly or transport across the IM, can be detected by regulatory sensors that 157 activate either the Cpx TCS or the alternative sigma factor σ E . σ E and Cpx are the two major 158 regulation pathways that control the envelop integrity with overlapping regulon members 159 [START_REF] Price | Characterization of the Cpx regulon in Escherichia coli strain 439 MC4100[END_REF][START_REF] Raivio | The Escherichia coli Cpx envelope stress 441 response regulates genes of diverse function that impact antibiotic resistance and membrane 442 integrity[END_REF][START_REF] Guest | A bacterial stress response regulates 444 respiratory protein complexes to control envelope stress adaptation[END_REF][START_REF] Dartigalongue | Characterization of the Escherichia coli 447 sigma E regulon[END_REF] but respond to different inducing cues [START_REF] Ruiz | Sensing external stress: watchdogs of the Escherichia coli cell 411 envelope[END_REF]. It is possible that these poorly defined 160 signals (see below) act by causing accumulation of misfolded proteins. However, misfolded 161 proteins are not the inducing signal per se, as some induce σ E but not Cpx and vice versa. [START_REF] Mizuno | A unique mechanism regulating gene expression: 501 translational inhibition by a complementary RNA transcript (micRNA)[END_REF][START_REF] Delihas | Discovery and characterization of the first non-coding RNA that regulates 504 gene expression, micF RNA: A historical perspective[END_REF][START_REF] Inouye | The first demonstration of RNA interference to inhibit mRNA function[END_REF]. This 93-nucleotide (nt) RNA is transcribed in the opposite direction to the ompC 196 gene and acts by direct base-pairing to a region that encompasses the ribosome binding site 197 (RBS) and the start codon of the ompF mRNA, thus preventing translation initiation [START_REF] Andersen | micF RNA binds to the 5' end of ompF mRNA and to a 508 protein from Escherichia coli[END_REF].

198

The expression of the MicF sRNA itself is subjected to multiple signals and regulatory 199 pathways [START_REF] Delihas | MicF: an antisense RNA gene involved in response of 510 Escherichia coli to global stress factors[END_REF]. Positive regulation includes EnvZ/OmpR in high osmolarity conditions [START_REF] Ramani | micF antisense RNA has a major role in 512 osmoregulation of OmpF in Escherichia coli[END_REF], 200 SoxS in response to oxidative stress [START_REF] Chou | Post-transcriptional repression of Escherichia 514 coli OmpF protein in response to redox stress: positive control of the micF antisense RNA by 515 the soxRS locus[END_REF] and MarA in response to antibiotic stress [START_REF] Cohen | MarA locus causes decreased expression of 383 OmpF porin in multiple-antibiotic-resistant (Mar) mutants of Escherichia coli[END_REF]. The

In

  Enterobacteriaceae, the development of MDR is under positive regulation by global 104 transcriptional activators that include members of Ara/XylS superfamily such as MarA, 105

112

  indicated that expression OmpX itself is controlled by a number of environmental factors 113 including salicylate via MarA and paraquat via SoxS [33] A very rapid MarA-dependent 114 response pathway for upregulation of ompX has been shown to occur within 60-120 min upon 115 cell exposure to salicylate [32]. This work by Dupont et al. identified dramatic decrease in 116 OmpF levels, as a first line of defense, with simultaneous development of resistance to β-117 lactams and fluoroquinolones by altering OM permeability.

120

  All living organisms have stress responses that allow them to sense and respond to 121 environmental damaging conditions by remodeling gene expression. As such, Gram-negative 122 bacteria possess stress responses that are uniquely targeted to the cell envelope, including 123 membranes and cell wall. These envelope stress responses (ESRs) are the EnvZ/OmpR, 124

162

  Recent studies rather suggest that Cpx responds to IM perturbations, while σ E is activated by 163 signals at the OM. The Cpx system comprises the CpxA sensor kinase and response regulator 164 CpxR. Envelope stresses including alkaline pH, periplasmic protein misfolding, IM 165 abnormalities such as misfolded transporters or accumulation of the lipid II precursor, induce 166 the dissociation of the accessory protein CpxP from CpxA, trigger CpxA-mediated 167 phosphorylation of CpxR, and altered expression of protein foldases and proteases, 168respiratory complexes, IM transporters, and cell wall biogenesis enzymes[START_REF] Raivio | Everything old is new again: an update on current research on the Cpx 415 envelope stress response[END_REF][START_REF] Price | Characterization of the Cpx regulon in Escherichia coli strain 439 MC4100[END_REF][START_REF] Raivio | The Escherichia coli Cpx envelope stress 441 response regulates genes of diverse function that impact antibiotic resistance and membrane 442 integrity[END_REF], all of 169 which affect resistance to a number of antibiotics, particularly aminoglycosides and β-170 lactams[START_REF] Raivio | Everything old is new again: an update on current research on the Cpx 415 envelope stress response[END_REF][START_REF] Raivio | The Escherichia coli Cpx envelope stress 441 response regulates genes of diverse function that impact antibiotic resistance and membrane 442 integrity[END_REF][START_REF] Guest | Role of the Gram-negative envelope stress response in the 449 presence of antimicrobial agents[END_REF][START_REF] Mahoney | The Cpx stress response confers resistance to some, but 451 not all, bactericidal antibiotics[END_REF][START_REF] Moreau | Protective role of the RpoE (σE) and Cpx envelope stress responses 453 against gentamicin killing of nongrowing Escherichia coli incubated under aerobic, 454 phosphate starvation conditions[END_REF]. The Cpx-mediated regulation of porins occurs at several levels. At 171 the transcriptional level, CpxR~P has been shown to bind directly the ompF and ompC 172 promoters[START_REF] Batchelor | The Escherichia coli CpxA-456 CpxR envelope stress response system regulates expression of the porins OmpF and OmpC[END_REF]. More recently, it has been found that the small IM protein MzrA connects Cpx and EnvZ/OmpR[START_REF] Gerken | MzrA: a novel 459 modulator of the EnvZ/OmpR two-component regulon[END_REF]. In this pathway and upon the activation of Cpx, MzrA interacts 174 directly with EnvZ, which in turn, stabilizes OmpR~P[START_REF] Gerken | MzrA-EnvZ interactions in the periplasm influence the 461 EnvZ/OmpR two-component regulon[END_REF]. In sensing different signals, the 175 interconnection between Cpx and EnvZ/OmpR allows cells to adapt to diverse environmental 176 stresses. Finally, although Cpx contributes to AMR by regulating a number of genes [37, 49, 177 52-54], its precise role and that of other TCSs in the development of MDR in clinical isolates 178 are still poorly documented[START_REF] Philippe | In vivo evolution of 463 bacterial resistance in two cases of Enterobacter aerogenes infections during treatment with 464 imipenem[END_REF]. On the other hand, the stress responsive sigma factor σ E is 179 induced by stresses that disturb the OM and its regulon members comprise genes that 180 facilitate the biogenesis of OM components, including proteins, lipoproteins and LPS [59-181 67]. In the absence of inducing signals, σ E is held at the cytoplasmic side of the IM by the 182 anti-sigma factor RseA. At the periplasmic side of the IM, RseB binds to RseA, thus 183 enhancing the inhibition of σ E . Upon activation, σ E is released from RseA by a proteolytic 184 cascade that starts with the sequential degradation of the periplasmic and transmembrane 185 domains of RseA by DegS and RseP, respectively, followed by the degradation of the 186 cytoplasmic domain of RseA by ClpXP [68]. Interestingly, proteolysis of RseA is triggered 187 by the binding of a conserved peptide found at the C-terminus of OM proteins, which is 188 normally buried in folded porin trimers, to DegS in conjunction with the release of RseB 189 from RseA upon binding of LPS intermediates [69, 70]. Of note, the σ E -dependent repression 190 of porin synthesis only occurs at the post-transcriptional level, wherein base-paring sRNAs 191 inhibits translation of omp mRNAs (see below) in order to maintain the envelope homeostasis 192 under stress conditions, as porins are major abundant proteins under normal growth 193 conditions [6]. 194 The post-transcriptional repression of OmpF by the sRNA MicF has been discovered in 1984 195

201 109 -

 109 nt MicC sRNA has been identified more recently and shown to repress OmpC by direct 202 base-pairing to a 5' untranslated region of the ompC mRNA[START_REF] Chen | MicC, a second small-RNA regulator of Omp 517 protein expression in Escherichia coli[END_REF]. Interestingly, micC is 203 transcribed in the opposite direction to the ompN gene that encodes a quiescent porin 204 homologous to OmpF and OmpC[START_REF] Prilipov | Identification and 519 characterization of two quiescent porin genes, nmpC and ompN, in Escherichia coli B E[END_REF]. We have recently shown that ompN and micC are 205 subjected to dual regulation upon exposure to certain antimicrobials such as β-lactams in a 206 σ E -dependent manner[START_REF] Dam | Dual regulation of the small RNA MicC and the 522 quiescent porin OmpN in response to antibiotic stress in Escherichia coli[END_REF]. This is consistent with that ompN-micC and ompC-micF share 207 similar genetic organization and that ompC and micF are co-induced under specific 208 conditions (i. e. high osmolarity via EnvZ/OmpR). The last decade has been marked by the 209 identification and characterization of several sRNAs. These are differentially expressed and 210 have been assigned to various important regulatory pathways in E. coli and Salmonella.211Interestingly, many pathways regulate and are regulated by sRNAs[START_REF] Thompson | SigmaE regulates and is regulated by a 427 small RNA in Escherichia coli[END_REF][START_REF] Vogt | The Cpx envelope stress response 429 regulates and is regulated by small noncoding RNAs[END_REF]. A prime 212 example is EnvZ/OmpR, which activates the expression of MicF (that target ompF), OmrA 213 and OmrB (that target ompT and mRNA of OM channels for iron-siderophore complexes) 214[START_REF] Guillier | Remodelling of the Escherichia coli outer membrane by 525 two small regulatory RNAs[END_REF]; OmrA and OmrB, in turn, repress the translation of the ompR mRNA, creating a 215 negative feedback loop[START_REF] Guillier | The 5' end of two redundant sRNAs is involved in the 527 regulation of multiple targets, including their own regulator[END_REF]. Others examples include the well-conserved σ E -regulated 216 sRNAs RybB (that target ompC and lamB in E. coli; ompN and ompW in Salmonella), MicA 217 (ompA), RseX (ompC and ompA), CyaR (ompX) and MicL (that represses translation of the 218 major OM lipoprotein Lpp) [43, 66, 83-90] (key figure). Of note all these sRNAs are trans-219 acting, function by imperfect base pairing with multiple mRNA targets and require the help 220 of the RNA chaperone Hfq [15-17]. 221 222 Porin alterations in clinical isolates 223 Combined regulations contributed by different stressors leads to hampering of the drug 224 accumulation inside cells under the threshold for bacterial death. In one such study in K. 225 pneumoniae, preferential expression of OmpK37 was detected in porin-deficient strains [92]. 226 Amino acid sequencing showed that OmpK37 is highly homologous to quiescent porins 227 OmpS2 from Salmonella enterica serovar Typhimurium and OmpN from E. coli. Liposome 228 swelling assay with purified porins determined that OmpK37 also has a narrower pore, which 229 was responsible for higher MICs of cefotaxime and cefoxitin antibiotics because of lower 230 drug diffusion. A very recent study identified mutation in the pho regulon of an extensively 231 drug resistant strain of K. pneumoniae demonstrating downregulation of phoE gene by 232 mutations in phoR and phoB. Here the PhoE porin, which is normally involved in phosphate 233 transport, promotes restoration of cefoxitin and carbapenem resistance [93]. This is an 234 interesting example of a regulatory mutation that effects porin expression, and clinically 235 favors AMR under antibiotic therapy. 236 A wide array of chemicals including disinfectants and antibiotics has been shown to modulate 237 the OM permeability including expression of porins [94]. In addition, several studies have 238 described the effect of imipenem on porin loss or loss of function mutations in clinical 239 isolates of Enterobacteriaceae [58, 95-100]. 240 Porins are trimers of 16-stranded β-barrels, each monomer formed of a central channel 241 constricted by loop 3 that folds inward, thereby restricting the size of the channel. The 242 presence of acidic residues in loop 3 facing a cluster of basic residues on the opposite side of 243 the pore creates a strong transversal electric field [6, 101, 102]. This so-called eyelet or 244 constriction region determines the channel size and ion selectivity, with OmpF being more 245 permeable than OmpC. This latter observation was first attributed to the OmpC pore being 246 slightly more constricted in this porin compared to OmpF [101, 102]. Although the two 247 porins share high sequence similarity, the pore interior is more negative in OmpC than in 248 OmpF [102]. This can also account for the low permeability of OmpC for anionic β-lactams 249 [103, 104]. Moreover, the replacement of all ten titratable residues that differ between OmpC 250 and OmpF in the pore-lining region leads to the exchange of antibiotic permeation properties 251 [105]. Together, these structural and functional data clearly demonstrate that the charge 252 distribution at pore linings, but not pore size, is a critical parameter that physiologically 253 distinguishes OmpC from OmpF. 254 Functional mutations in porin genes leading to reduced permeability are another strategy 255 found in MDR bacteria. In two documented cases, β-lactam-resistant clinical isolates of E.256 aerogenes contained Omp36 (an OmpC homologue) that carried the mutation G112D in L3 257 [106, 97]. The homologous mutation G119D in OmpF of E. coli narrows the size of the 258 channel as the large side chain of Asp protrudes into the channel lumen and confers a drastic 259 reduction in β-lactam susceptibility [107]. Consistently, the Omp36 G112D mutant of E.

  260aerogenes was characterized by a 3-fold decrease in ion conductance and a significant 261 decrease in cephalosporin sensitivity (e. g. MICs of cefotaxime, cefpirome, cefepime and 262 ceftazidime were 7 to 9 fold higher in the clinical isolate as compared to that in a sensitive 263 reference strain) and a cross resistance to carbapenems[106,[START_REF] Thiolas | Resistance to imipenem, 569 cefepime, and cefpirome associated with mutation in Omp36 osmoporin of Enterobacter 570 aerogenes[END_REF]. Recent studies also found a 264 series of OmpC mutants that were isolated from a patient with chronic E. coli infection and 265 additive mutations that conferred increased resistance to a variety of antibiotics, including 266 cefotaxime, ceftazidime, imipenem, meropenem and ciprofloxacin [108, 109]. Low et al. 267 demonstrated that subtle changes in OmpC in clinical isolates of E. coli altered antibiotic 268 permeability and thus cell viability [108]. Seven isolates collected over a two year clinical 269 treatment exhibited increased levels of antibiotic resistance. These isolates exhibited the same 270 two mutations (D18E and S274F) in the OmpC porin with increased levels of antibiotic 271 resistance, thus pointing towards the possible functional role of these mutations in antibiotic 272 influx. 273 It is worthwhile to note that from our knowledge, porin mutations causing reduced 274 permeability have only been described in OmpC-type porins in E coli and E aerogenes. 275 Interestingly, this type of porin is expressed under high osmolarity, the same environment the 276 bacteria encounters the hosts. This gives an essential outlook on the host induced 277 modifications that possibly occurs in these pathogens during infection. Heeding to this sort of 278 information can be highly beneficial for designing drugs with an improved diffusion across 279 the bacterial outer membrane. 280 281 Conclusion 282 It is noteworthy that the sRNA-mediated stress response mechanism has multiple benefits for 283 bacteria as compared to regulation by protein. Since sRNAs are produced during 284 transcription, the later stages of translation and post translational modification processes in 285 the cell is completely skipped proving to be time and energy efficient for the cell. Not to 286 forget the energy saved in porin assembly and discarding of misfolded proteins, which in 287 itself can induce another stress response mechanism. 288 Decreased porin expression has been observed as a rapid response to toxic molecules and 289 antibiotics within less than 60 minutes. Many sRNAs act at the post-transcriptional level, 290 which ensures a rapid response to stressful conditions. In addition, the versatility of sRNAs 291 ensures another level of gene regulation along with protein transcriptional regulators, thus 292 contributing to an additional layer of tighter regulation. Taking into account the major role of 293 the CpxAR and EnvZ/OmpR regulators in response to stressors such as antibiotics, it will be 294 interesting to develop some assays allowing the detection of these kinds of mutations inside 295 clinical isolate. This original diagnostic maybe used for determining the prevalence of these 296 regulation events in clinical strain that have undergone antibiotic stress. 297 Targeting the early transcriptional step of antibiotic stress response regulatory mechanism is 298 much more logical, especially when we have reports of OMP expression being regulated 299 (both up and downregulation) within 60 minutes of stress appearance [32]. This will 300 especially promote bypassing of aforementioned mutations in porins in clinical strains that 301 are selected during antibiotic treatment. Targeting of sRNA or sRNA regulators such as 302 MicF or Hfq can rejuvenate failing antimicrobial therapies in regards with membrane 303 impermeability. They can be original targets for increasing the efficiency of existing drugs by 304 providing fitness reduction in bacteria. As of now, a cyclic peptide RI20 has been identified 305 to inhibit Hfq-mediated repression of gene, by binding with proximal binding site of Hfq 306 [110]. Another approach will be to inhibit sRNA interfering with porin expression that is 307 involved in drug translocation. Recently, a small molecule was used to target human 308 microRNA (miR)-525 precursors as an anti-cancer strategy [111]. This promising discovery 309 can be repeated in bacteria for manipulating sRNA levels, which may save the failing 310 antibiotic therapies. 311 Predictability of an efficient drug based on the SICAR (Structure Intracellular Concentration 312 Activity Relationship) concept, is a step up to efficient drug designing. Briefly, SICAR 313 connects the physicochemical drug properties to the efficacy of translocation through the 314 bacterial membrane and the resulting intracellular accumulation. To achieve this goal, an 315 extensive knowledge of the OM permeability control, including the contribution of sRNAs, is 316 required.

  317

Acknowledgments:

We thank all the members of the UMR_MD1, especially Estelle Dumont 323 and Julia Vergalli, for helpful discussions throughout this work.

324 325

Funding information:

The research leading to the discussions presented here was conducted RseP at the periplasmic and the cytoplasmic site. Another protease, ClpXP specifically 619 degrades the cytoplasmic RseA portion bound to σ E , leading to its release. A number of σ E -620 regulated sRNAs are indicated: MicC [START_REF] Chen | MicC, a second small-RNA regulator of Omp 517 protein expression in Escherichia coli[END_REF] downregulates OmpC and is coupled with ompN 621 upregulation [START_REF] Dam | Dual regulation of the small RNA MicC and the 522 quiescent porin OmpN in response to antibiotic stress in Escherichia coli[END_REF]; sRNA regulation of porins via CyaR [START_REF] Johansen | Down-regulation of 549 outer membrane proteins by noncoding RNAs: unraveling the cAMP-CRP-and sigmaE-550 dependent CyaR-OmpX regulatory case[END_REF], IpeX [START_REF] Castillo-Keller | Novel mechanism of Escherichia coli porin 552 regulation[END_REF], RseX [START_REF] Douchin | Down-regulation of porins by a small RNA bypasses 539 the essentiality of the regulated intramembrane proteolysis protease RseP in Escherichia coli[END_REF] and RybB 622 [START_REF] Johansen | Conserved small 533 non-coding RNAs that belong to the sigmaE regulon: role in down-regulation of outer 534 membrane proteins[END_REF][START_REF] Bossi | A small RNA downregulates LamB maltoporin in 545 Salmonella[END_REF] are shown accompanied by their activators and porin targets; CyaR negatively 623 regulates the expression of single channeled porin OmpX [START_REF] Dupont | Enterobacter aerogenes 397 OmpX, a cation-selective channel mar-and osmo-regulated[END_REF], which in turn negatively


Erwan Lecarpentier

Guillaume Infantes

Charles Lesire

Emmanuel Rachelson
email: emmanuel.rachelson@isae-supaero.fr

Open Loop Execution of Tree-Search Algorithms

Keywords: Model-based Reinforcement Learning, Tree Search Algorithms, Open Loop Control, Markov Decision Processes

published or not. The documents may come

Introduction

Tree-search based algorithms recently encountered a real success at solving sequential, highly combinatorial problems such as the challenging game of Go [START_REF] Enzenberger | Fuego -an open-source framework for board games and go engine based on monte carlo tree search[END_REF][START_REF] Silver | Mastering the game of go with deep neural networks and tree search[END_REF]. Such algorithms use a generative model of the environment to simulate episodes starting from the current state of the agent [START_REF] Richard S Sutton | Dyna, an integrated architecture for learning, planning, and reacting[END_REF][START_REF] Richard | Reinforcement learning: An introduction[END_REF]]. This allows the exploration of reachable states and actions and results in the construction of an (unbalanced) scenario tree, that aims at identifying promising branches with a limited computational budget. When the computational budget is exhausted, the recommended action at the root node is applied and a new tree is built in the resulting state. This results overall in a closed loop control process. We are interested in stochastic problems with large state spaces (e.g. continuous) with a short decision time (bud-get). In this setting, open loop planning algorithms have proven to be successful [START_REF] Bubeck | Open loop optimistic planning[END_REF] and even to outperform [START_REF] Weinstein | Bandit-based planning and learning in continuous-action markov decision processes[END_REF] the standard approaches that consider closed loop policy trees such as UCT [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF]. They seek for optimal sequences of actions (plans) rather than optimal policies despite the sub-optimal nature of a plan in stochastic environments. Indeed, computing the latter prevents feedback on the explored states but allows to break the complexity of the state space exploration. Given a tree computed by an open loop planning algorithm, we propose to keep the sub-tree reached by the application of the recommended action and to directly use it as the main tree for the subsequent time step, without re-planning. What motivates this approach is the saving of the computational cost of tree building for subsequent time steps, hence the reduction of number of calls to the simulator. This feature is highly desirable for agents with short decision time, for instance with a high control frequency (e.g. robots torque control) or low computational resources (e.g. satellite systems). In this framework, Perez et al. [2012a] and Heusner [2011] considered keeping the tree in deterministic environments but observed a negative impact as the sub-trees were systematically kept without analysis.

In this paper, we study the impact of using the subsequent sub-trees as main trees for the next action steps without further re-planning. We claim that in lowly-stochastic environments, the reached performance is comparable to algorithms systematically discarding the tree. Our contribution is threefold. (1) We introduce a new algorithm called OLTA (Section 3), performing a systematic analysis of the sub-tree and taking the decision of re-planning or not at each time step. (2) We upper bound the probability of selecting a suboptimal action within a sub-tree, the sense of optimality being defined in an open loop fashion (Section 4). Additionally, we show that this upper bound decays logarithmically with the sub-tree depth. (3) We show in our experiments the benefit of applying such a method both in terms of performance and computational cost saving (Section 5).

The structure of the paper is as follows: first we set the mathematical background in Section 2; then we introduce the OLTA algorithm in Section 3; we perform a theoretical analysis in Section 4, followed by an empirical study in Section 5; finally we conclude in Section 6.

Background

Markov Decision Process

We model the planning problem as a Markov Decision Process (MDP) where an agent sequentially takes actions with the general goal of maximizing the cumulative return fed back by the environment [START_REF] Martin L Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]. We refer to the state space as S and the action space as A. We suppose the number of actions to be finite with K = |A|, thus we write A = {a i } K i=1 . We also consider that the available actions are independent of the state the agent lies in. The state transition function is stochastic and we note P (s |s, a) the probability of reaching state s after taking action a in state s. The reward model is denoted by r(s, a, s ) and refers to the scalar reward received while performing the transition (s, a, s ). We assume that this reward function is deterministic. Finally, we suppose the horizon of the MDP is infinite and we note γ ∈ [0, 1[ the discount factor which represents the importance of the subsequent collected rewards.

Tree Representation

When a generative model of the MDP is available, it becomes possible to use it within planning algorithms. Treesearch algorithms use this model in order to build a tree of what may possibly occur in the current situation of the agent [START_REF] Richard S Sutton | Dyna, an integrated architecture for learning, planning, and reacting[END_REF][START_REF] Richard | Reinforcement learning: An introduction[END_REF][START_REF] Silver | Sample-based learning and search with permanent and transient memories[END_REF]. In the stochastic setting with potentially infinitely many states, we use a tree structure similar to the one used by [START_REF] Bubeck | Open loop optimistic planning[END_REF]. The tree built at each time step consists in a look-ahead search of the possible outcomes while following some action plan starting from the current state of the agent s 0 ∈ S. Thus, the root node of the tree is labelled by the unique state s 0 . The edges correspond to the K available actions, K being the branching factor of the tree. The tree itself conforms to an ensemble of action sequences, or plans, originating from its root node. We emphasize the fact that this tree structure implies that we search for a state-independent optimal sequence of actions (open loop plan) which is in general sub-optimal compared to a state-dependent policy search. The THTS family of algorithms in particular [START_REF] Keller | Trial-based heuristic tree search for finite horizon mdps[END_REF] defines trees with chance and decision nodes while our structure does not apply an equality operator on the sampled states. Following [START_REF] Bubeck | Open loop optimistic planning[END_REF], [START_REF] Weinstein | Bandit-based planning and learning in continuous-action markov decision processes[END_REF], we argue that closed-loop application of the first action in optimal open loop plans, although theoretically suboptimal, can be competitive with these methods in practice, while being more sampleefficient. Since the transition model is stochastic, the non-root nodes

Root node

Non-root node

s 0 a 1 a i s 1 s l a K d = 0 d = 1 ∀i ∈ {1, • • • , l} , s i ∼ P (•|s 0 , a i ) a 1 a K • • • • • • • • • • • • Figure 1:
General representation of a tree, where l ∈ N is the number of times the sub-tree reached by action a i has been developed. Two nodes are represented in this tree with their respective depths on the left.

are not labelled by a unique state. Instead, every such node is associated to a state distribution resulting from the application of the action plan leading to the considered node and starting from s 0 . During the exploration, we consider saving all sampled states at each non-root node. A comprehensive illustration of such a tree can be found in Figure 1. This approach extends straightforwardly to Partially Observable Markov Decision Processes (POMDP) [START_REF] Silver | Monte-carlo planning in large pomdps[END_REF]. Given a tree-search, open loop planning algorithm, we call T d the tree at depth d ∈ N, that is the sub-tree resulting from the application of the d first recommended actions. Hence T 0 denotes the whole tree, T 1 the tree starting from the node reached by the application of the first recommended action and so on.

Open Loop UCT

For the sake of clarity and in order to clearly separate the tree building properties from the open loop execution presented in the next section, we define an open loop planning algorithm utilizing the presented tree structure that we call Open Loop UCT (OLUCT). The difference between UCT and OLUCT is that OLUCT is not provided with an equality operator over states. Within the THTS terminology, this means that decision and chance nodes do not correspond to a single state but to the state distribution reachable by the action plan leading to the node. Hence decision and chance nodes are associated to the state distribution which makes OLUCT an open loop planning algorithm. The fundamental consequence is that an action value within our tree is computed w.r.t. the parent node's state distribution rather than a single state. Apart from this, OLUCT uses the same exploration procedure as UCT. Within a node, we note X i,u the estimated expected return of action i after u samples of this action. T i (t) is the number of trials of action i up to time t of the OLUCT procedure. An Upper Confidence Bound (UCB) strategy [START_REF] Auer | Finitetime analysis of the multiarmed bandit problem[END_REF] is applied at each node where each action corresponds to an arm of a bandit problem.

The tree policy selects the action I t with the highest UCB:

I t = arg max i∈{1,••• ,K} X i,Ti(t-1) + c t-1,Ti(t-1) , (1)
where c t,u is an exploration term ensuring that all actions will be sampled infinitely often (Equation 2).

c t,u = 2C p ln(t) u (2)
The C p parameter drives the exploration-exploitation trade-off. The OLUCT tree building procedure is detailed in Algorithm 1.

Algorithm 1: OLUCT tree building procedure Backup(ν leaf , ∆); // Back-propagate the sampled return.

return T (ν root )

3 OLTA (Open Loop Tree-search Algorithm)

Description

In order to control the execution of open loop plans, we propose a new algorithm called OLTA (Algorithm 2). It relies on a generic open loop planning algorithm to generate a tree, rooting from the current state. For the next execution time step, it decides either to use the sub-tree reached by the recommended action or to trigger a re-planning by building a new tree. If no re-planning is triggered, then the recommended action of the sub-tree is applied without using the additional information of the new state observed after the transition. This results in an open loop control process and spares the cost of developing a new tree starting at this state. The intuition behind OLTA is that several consecutive recommended actions in an optimal branch of the tree can be reliable, despite the randomness of the environment. A major example of such a case is low-level control, where consecutive sampled states are close to each other.

In this paper, for its performance and simplicity, we chose to implement OLUCT as the open loop planning algorithm utilized by OLTA. However, any other algorithm generating trees as described in Section 2.2 could be used in the same way (e.g. OLOP [START_REF] Bubeck | Open loop optimistic planning[END_REF], or HOLOP [START_REF] Weinstein | Bandit-based planning and learning in continuous-action markov decision processes[END_REF]). One important feature of OLTA is the so-called "decision-Criterion", based on which the agent decides to either use the first sub-tree following the recommended action, or to re-build a new tree from the current state. The decision is based on a comparison with the characteristics of the resulting sub-tree and the current state of the agent. In the next section, we discuss different decision criteria, leading to the consideration of a family of different algorithms.

Algorithm s := realWorldTransitionFunction(s, a);

Decision Criterion

The simplest implementation of the decision criterion is to keep the sub-tree only if its root node is fully expanded. This means that each action has been sampled at least once. We call the resulting algorithm Plain OLTA. It naively trusts the value estimates of the sub-tree, thus applies the whole plan of recommended actions at each depth until it reaches a partially expanded node. Therefore, Plain OLTA is expected to perform better in deterministic environments. In stochastic cases however, those estimates may be biased because of the different sources of uncertainty within the MDP (reward function, state transition function and action selection). For this reason, we seek more robust criteria to base the decision on.

A natural way to decide whether to keep the sub-tree or not is to track if the recommended action is optimal w.r.t. the new state s of the agent. Here we make an important distinction between a state-wise optimal action and a nodewise optimal action. The first one is the action recommended by the optimal policy in a specific state. We note it a * = arg max a∈A Q * (s, a), with Q * : S × A → R the optimal state-action value function. In order to define the second one, we introduce S d , the state random variable at the root node of T d . Its distribution results from the application of the d first recommended actions starting from s 0 , so

S d ∼ P (•|s 0 , a 0 , • • • , a d-1 ) ≡ P S d (•).
The node-wise optimal action maximizes the expected return given the state distribution of the node. We note it

a * d = arg max a∈A Q * d (a) where Q * d : A → R
Q π (s, a) = E π (X(s, a)) Q π d (a) = E P S d (Q π (s, a)) with X(s, a) ∼ R(s, a) + γP π X(s, a) and S d ∼ P S d (•).
Unfortunately, at the root node of T d for d > 0, open loop tree-search algorithms do not estimate

Q * but Q * d .
The bias introduced by the state distribution implies that in the general case we have no guarantee that a * = a * d . The risk is that the set Ω S d of possible realizations of S d can include states where a * is sub-optimal, in which case the resulting return evaluations would weight in favour of a different action than a * . In other words -introducing the notion of domination domain for an action a as D a = {s ∈ S|π * (s) = a} ⊂ S -if Ω S d is not included in D a * , then the risk of the recommended action to be state-wise sub-optimal is increased. Conversely, if Ω S d is included in the domination domain of a * , then the optimal action will be selected given that the budget is "big enough" w.r.t. the chosen tree-search algorithm's performance. Consequently, one should base the decision criterion on the analysis of P S d and the action domination domains. To compute these domains, [START_REF] Rachelson | On the locality of action domination in sequential decision making[END_REF] use the properties of Lipschitz-MDPs. Although the following discussion is inspired by this work, the consideration of Lipschitz-MDPs is out of the scope of this paper. We discuss below the construction of decision criteria that will be illustrated in Section 5. Current state analysis & POMDP setting. The current state s of the agent can be compared to the empirical state distribution P S d at the root node of the sub-tree. If P S d (s) is large, then the value estimators are related to the locality of the state space the agent lies in. If not, then the node-wise optimal action may not be state-wise optimal. This consideration supposes to identify a state-metric for which two close states have a high chance to be in the same action domination domain. Alternatively, in the case of a POMDP, a belief distribution on the current state is available instead of the current state itself [START_REF] Pack | Planning and acting in partially observable stochastic domains[END_REF]]. In such a case, a direct comparison between this distribution and P S d can be performed (e.g. with a Wasserstein metric). State distribution analysis. The dispersion and multimodality of P S d could motivate not to re-use a sub-tree. A high dispersion involves the possibility that Ω S d does not belong to a single action domination domain and a re-planning should be triggered. The same consideration applies in terms of multi-modality. Conversely, a narrow, mono-modal, state distribution is a good hint for Ω S d to be comprised into a single action domination domain. Return distribution analysis. A widespread or a multimodal return distribution for the recommended action in a node may indicate a strong dependency on the region of the state space we lie in. If Ω S d covers different action domination domains, each of these domains may contribute a different return distribution to the node's return estimates, thus inducing a high variance on this distribution or even a multi-modality. In this case, it could be beneficial to trigger the re-planning. Alternatively, even after re-planning, widespread or multi-modal return distributions can naturally arise as a result of the MDP's reward and transition models. We do not provide a unique generic method to base the decision criterion on. Indeed, we believe that it is a strongly problem-dependent issue and that efficient heuristics can be built accordingly. However, the analysis of the state and return distributions constitute promising indicators and we exemplify their use in the experiments of the last section.

Theoretical Analysis

In this section, we demonstrate that the algorithm asymptotically provides node-wise optimal actions for any subtree T d of depth d. We first derive an upper bound on the failure probability that converges towards zero when the initial budget n of the algorithm goes to infinity. Then, we characterize the loss of performance guarantees between subsequent depths and show a logarithmic decay of the upper bound. The demonstration unfolds as follows: first we write a lower bound for the number of trials of the actions at the root of T d in Lemma 1; then we write an upper bound on the failure probability given a known budget at depth d in Lemma 2; finally we derive a recursive relation between the upper bounds of subsequent trees that leads to our result in Theorem 1. We note b(d) ∈ N the budget used to develop T d i.e. the number of times the d first recommended actions have been selected by the tree policy. We note T d i,t the number of times the i th action at the root node of T d has been selected by the OLUCT tree policy after t expansions of T d . Similarly, X d i,T d i,t ≡ X d i,t denotes the estimate of the return of the i th action at depth d after t expansions of the sub-tree T d . We write I d t the index of the action chosen by the tree policy at depth d after t expansions of T d . We have:

I d t = arg max i∈{1,••• ,K} X d i,t-1 + c t-1,T d i,t-1
The recommended action at depth d given a budget b(d) is

I d = arg max i∈{1,••• ,K} X d i,b(d)
. Following [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF], we assume that the empirical estimates X d i,t converge and write

X d i,t = E{X d i,t } and X d i = lim t→∞ X d i,t . Then, we define for i ∈ {1, • • • , K} \ i * d , ∆ d i = X d i * d -X d i
where we note i * d the index of the nodewise optimal action at the root node of T d . We make the hypothesis that only one action is optimal in a given node. The minimum return difference between a suboptimal action and the optimal one at depth Proof. The first result is borrowed from [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF] where they show it for a generic bandit problem. The extension to our case with a given budget is straightforward. The sequence of lower bounds can be derived by observing that b(d

d is δ d = min i∈{1,••• ,K}\i * d (∆ d i ).
) = T d-1 I d-1 ,b(d-1
) and applying the previous lower bound.

P ( I d = i * d |b(d)) ≤ b(d) -ρ 2 (δ d ) 2
Proof. Let us first bound the failure probability with the probability of overestimating a suboptimal action and underestimating the optimal one up to

∆ d I d /2. P I d = i * d b(d) = P X d I d ,b(d) ≥ X d i * d ,b(d) b(d) ≤ P X d I d ,b(d) ≥ X d I d ,b(d) + ∆ d I d 2 ∪ X d i * d ,b(d) ≤ X d i * d ,b(d) - ∆ d I d 2 b(d) ≤ P X d I d ,b(d) ≥ X d I d ,b(d) + ∆ d I d 2 b(d) + P X d i * d ,b(d) ≤ X d i * d ,b(d) - ∆ d I d 2 b(d)
From now on, the proof breaks to the analysis of one of the two terms on the right of the last inequality since both can be considered the same way. Let us consider the first term:

P X d I d ,b(d) ≥ X d I d ,b(d) + ∆ d I d 2 b(d) = b(d) t=1 P X d I d ,b(d) ≥ X d I d ,b(d) + ∆ d I d 2 T d I d ,b(d) = t × P T d I d ,b(d) = t b(d) ≤ b(d) t=1 exp - 1 2 (∆ d I d ) 2 t P T d I d ,b(d) = t b(d) ≤ b(d) t= ρ ln(b(d)) exp - 1 2 (∆ d I d ) 2 t P T d I d ,b(d) = t b(d) ≤ exp - 1 2 (∆ d I d ) 2 ρ ln(b(d)) ≤ b(d) -ρ 2 (δ d ) 2
Where we first write the joint probability, then apply Hoeffding's inequality, followed by Lemma 1 and the fact that a convex combination is upper bounded by its higher element. Similarly to [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF], we shall assume that the UCT constant C p is appropriately chosen for the tail inequalities to be verified.

Theorem 1. Upper bound on the failure probability at depth d. For an initial budget of n and for any sub-tree T d developed with a budget b(d) > K, we have the following recursive relation for the upper bound on the failure probability, conditioned by the initial budget n:

P ( I d = i * d |n) ≤ ρ ln(b(d -1)) -ρ 2 (δ d ) 2
Additionally, for any depth d ≥ 1 given the initial budget n:

P ( I d = i * d |n) ≤ f d (n) -ρ 2 (δ d ) 2 f : t → ρ ln(t)
Where

f d = f • f d-1 with f 1 = f and d > 0.
Proof. We write the joint probability distribution:

P ( I d = i * d |n) = n t=1 P ( I d = i * d |n, b(d) = t)P (b(d) = t|n) ≤ n t=1 t -ρ 2 (δ d ) 2 P (b(d) = t|n) ≤ n t= ρ ln(b(d-1)) t -ρ 2 (δ d ) 2 P (b(d) = t|n) ≤ ρ ln(b(d -1)) -ρ 2 (δ d ) 2
Where we first applied Lemma 2 and then used the fact that b

(d) = T d-1 I d-1 ,b(d-1
) onto which we apply Lemma 1. Finally, we use the fact that a convex combination is upper bounded by its higher element. The last result comes from the sequence of lower bounds in Lemma 1. This result shows a logarithmic decay between the upper bounds on the failure probability of two subsequent trees. Asymptotically, at any depth, this upper bound converges towards zero. This result highlights the fact that the deeper the sub-tree is, the less one can rely on the recommended action at the root node. However, we should note that these upper bounds are derived without making further hypotheses on the MDP and express a worst-case value. We show in the next section that equal performances to OLUCT can be reached with a smaller computational budget and number of calls to the generative model.

s 0 r = 1 s 1 r = 0 s 2 r = 0 s 3 r = 0 s 4 r = 1

Empirical Analysis

We compared OLUCT with OLTA on a discrete 1D track environment 1 and within a continuous Physical Travelling Salesman Problem 2 (PTSP) [Perez et al., 2012b]. We implemented five decision criteria, leading to five variations of OLTA.

Heuristic decision criteria

A relevant decision criterion w.r.t. the treated problem allows OLTA to discard a sub-tree when its first recommended action may not be state-wise optimal given the current state of the agent. We implemented five different tests to base this decision on, and evaluated them independently, which led to the following variations of OLTA. Plain OLTA. The simplest decision criterion that discards a sub-tree only if its root-node is not fully expanded. State Distribution Modality (SDM-OLTA). Test whether the empirical state distribution is multi-modal or not. If yes, discard the tree if the current state of the agent does not belong to a majority mode. We define a majority mode by a mode comprising more than τ SDM % of the sampled states. State Distribution Variance (SDV-OLTA). Test whether the empirical state distribution variance is above a certain threshold τ SDV . Discard the tree if it is the case. For multidimensional state spaces such as in the PTSP, the Variance-Mean-Ratio (VMR) is considered for the different orders of magnitude to be comparable.

State Distance to State Distribution (SDSD-OLTA).

Compute the Mahalanobis distance [START_REF] De Maesschalck | The mahalanobis distance. Chemometrics and intelligent laboratory systems[END_REF] of the current state from the empirical state distribution. Discard the tree if it is above a selected threshold 1 Code available at: τ SDSD .

Return Distribution Variance (RDV-OLTA). Test whether the empirical return distribution variance is above a certain threshold τ RDV . Discard the tree if it is the case.

A more selective decision criterion can easily be derived by combining the previously described decision criteria and discarding the tree if one of them recommends to do so.

1D Track Environment

The 1D track environment (Figure 2), is a 1D discrete world where an agent can either go right or left. The initial state is the "middle" state s 0 = s 2 . The reward is 0 everywhere except for the transition to the two terminal states s 0 and s 4 for which it is +1. The action space is A = {right, lef t}. We introduce a transition misstep probability q ∈ [0, 1] which is the probability to end up in the opposite state after taking an action, for i ∈ {1, 2, 3}: P (s i-1 |s i , right) = q and P (s i+1 |s i , right) = 1q.

The same applies for the lef t action. If q < 0.5, the optimal policy π optimal is to go left at s 1 , to act randomly at s 2 and to go right at s 3 . The simulation settings are: q ∈ {0.0, 0.05, • • • , 0.5}; n = 20 (budget); π def ault = π optimal ; H = 10 (simulation horizon for π def ault ); C p = 0.7; γ = 0.9. The decision criteria parameters were tuned to: τ SDM = 80; τ SDV = 0.4; τ SDSD = 1; τ RDV = 0.9. We generated 1000 episodes for each value of q and recorded 3 performance measures: loss (number of time steps to termination); computational cost (measured computation time); and number of calls to the generative model. We display two different graphs of the loss, the second one highlights the relative performance The motivation behind the use of such a benchmark is to test open loop control in a highly stochastic environment where feedback of the current state is highly informative about the optimal action. In case of misstep for the first action, OLTA has to guess that a re-planning should be triggered while OLUCT does it systematically. As seen on Figure 3, the non-plain OLTA and OLUCT achieved a very comparable loss. Plain-OLTA had a weaker performance due to its systematic re-use of the sub-trees. In terms of both computational cost and number of calls to the generative model, OLTA widely outperforms OLUCT. As q increases, this computational gain vanishes and catches up with OLUCT for SDM-OLTA and SDV-OLTA. This accounts for the discriminative power of their decision criteria that discard more trees. RDV-OLTA and SDSD-OLTA kept a lower computational cost while reasonably matching the performance of OLUCT. Obviously, the computational cost of Plain-OLTA stays low. The apparent similarity between the number of calls to the generative model and the computational cost proves that computing our decision criteria is less expensive than re-planning.

Physical Travelling Salesman Problem

The PTSP is a continuous navigation problem in which an agent must reach all the waypoints within a maze (Figure 4). The state of the agent is s = (x, y, θ, v) ∈ R 4 i.e. the 2D position, orientation and velocity. The action space is A = {+dθ, 0, -dθ} which consists of the increment, decrement or no-change of the orientation. The reward is +1 when a waypoint is reached for the first time, -1 for a wall crash and 0 otherwise. The simulation terminates when the agent reaches all the waypoints or time limit. The walls cannot be crossed and the orientation is flipped when a crash occurs. We introduce a misstep probability q ∈ [0, 1] which is the probability for another action to be undertaken instead of the current one. A Gaussian noise of standard deviation σ noise is added to each component of the resulting state from a transition. The simulation settings are: s 0 = (1.1, 1.1, 0, 0.1); q ∈ {0.0, 0.05, • • • , 0.5}; σ noise = 0.02; n = 300 (initial tree budget); π def ault = π go-straight that applies no orientation variation; H = 50 (simulation horizon for π def ault ); C p = 0.7; γ = 0.99. The provided map is the one depicted in Figure 4 cision criteria parameters were tuned to: τ SDV = 0.02; τ SDSD = 1; τ RDV = 0.1. We reserve the development of SDM-OLTA in the continuous case for future work. We generated 100 episodes for each transition misstep probability and recorded the same performance measures as in the 1D track case. The results are presented in Figure 5. OLUCT, SDSD-OLTA and RDV-OLTA achieved a comparable loss for every q, which shows that our method is applicable to larger scale problems than the 1D track environment. SDV-OLTA reached a lower level of performance. Plain OLTA still realized the highest loss since it is highly sensitive to the stochasticity of the environment.

In terms of both computational cost and number of calls to the generative model, the same trade-off between performance and computational cost can be observed. Plain OLTA and SDV-OLTA considerably lowered the number of calls at the cost of the performance while SDSD-OLTA and RDV-OLTA realized a better compromise. The number of calls to the generative model and the computational cost are quite similar, meaning that -even with the higher dimensionality of the PTSP compared to the 1D track -the cost incurred by the decision criteria computation is negligible in comparison to the one incurred by the re-planning procedure. Notice that SDV-OLTA achieved a good costperformance trade-off in the 1D track environment while not in the PTSP relatively to the other algorithms. This is explained by the decision criteria's sensitivity to parameter tuning and by the problem-dependent relevance of such a criterion.

We introduced OLTA, a new class of tree-search algorithms performing open loop control by re-using subsequent subtrees of a main tree built with the OLUCT algorithm. A decision criterion based on the analysis of the current state and the current sub-tree allows the agent to efficiently determine if the latter can be exploited. Practically, OLTA can achieve the same level of performance as OLUCT given that the decision criterion is well designed. Furthermore, the computational cost is strongly lowered by decreasing the number of calls to the generative model which is the interest of the approach. We emphasize the fact that this method is generic and can be combined with any other treesearch algorithm than OLUCT. Open questions include building non problem-dependent decision criteria, e.g. by making more restrictive hypothesis on the considered class of MDPs, but also applying the method to other benchmarks and other open loop planners.

  else T = createTree(s); // Create a new tree from the current state. a = recommendedAction(T ); // Get the first recommended action.T = subTree(T , a); // Move the tree to the first sub-tree resulting from the application of a.

  is the optimal action value function w.r.t. the state distribution at the root node of T d , that is Q * d (a) = E s∼P S d (Q * (s, a)). Following Bellemare et al. [2017], a distributional Bellman equation can be expressed in terms of three sources of randomness that are: R : S × A → R the stochastic reward function; X : S × A → R the random return; and P π the transition operator with P π X(s, a) D := X(S , A ), S ∼ P (•|s, a) and A ∼ π(•|S ). Mathematically, we have the following distributional Bellman equations:

Lemma 1 .

 1 Lower bound for the number of trials. For any sub-tree T d developed with a budget b(d) > K, there exist a constant ρ ≥ 0 such that T d i,b(d) ≥ ρ ln(b(d)) for all i ∈ {1, • • • , K}. Furthermore, we have the following sequence of lower bounds for the budget with • the ceiling function: b(d = 0) = n b(d) ≥ ρ ln(b(d -1))

Lemma 2 .

 2 Upper bound on the failure probability at depth d given the budget b(d). For any sub-tree T d developed with a budget b(d) > K we have the following upper bound on the failure probability, conditioned by the budget b(d):

Figure 2 :

 2 Figure 2: 1D track environment. On top of each cell representing a state is the immediate reward of the transition to this state.

Figure 3 :

 3 Figure 3: Comparison between OLUCT and OLTA on the discrete 1D track environment for varying values of q.

  an OLUCT algorithm in our PTSP setting. The starting point is displayed in red, the waypoints in green and the walls in grey.

Figure

  Figure 4: PTSP illustration

Figure 5 :

 5 Figure 5: Comparison between OLUCT and OLTA on the continuous PTSP for varying values of q.

  2: OLTA algorithm

	Function OLTA:
	Parameters: initial state s 0 ; tree building procedure
	createTree; re-planning criterion decisionCriterion.
	s = s 0 ;
	T = createTree(s); while s is not terminal do
	if decisionCriterion(s, T ) then a = recommendedAction(T ); // Get the first
	recommended action.


Abdelmalek Aboussoror

Samir Adly
email: samir.adly@unilim.fr

Generalized Semi-Infinite

Keywords: Programming: Optimality Conditions Involving Reverse Convex Problems Convex analysis, Generalized semi-infinite programming problems, Optimality conditions, Stability. Mathematics Subject Classification 90C34, 90C46, 90C31, 46N10

HAL is

INTRODUCTION

We consider the following generalized semi-infinite programming problem

(S ) min x∈X G (x,y)≤0, ∀ y∈Y (x) F (x),
where F : p → , G : p × q → are functions, X is a nonempty subset of p , and Y (x) is an infinite index subset of q depending on x, defined by Y (x) = y ∈ q /g (x, y) ≤ 0 , where g : p × q → is a function.

1

Note that semi-infinite programming problems differ from generalized semi-infinite programming problems by the fact that the index set Y (x) does not depend on the decision variable x. The class of generalized semi-infinite programming problems has several applications. We cite, for example, approximation theory, economics, optimal control, and engineering.

In this article, we investigate a class of nonsmooth generalized semiinfinite programming problems of the form of (S ) whose feasible sets are represented by a reverse convex constraint; that is, a constraint of the form h(x) ≥ 0, with h : p → is a convex function. So that, in addition to the tools of convex analysis, the use of some results related to reverse convex problems will play an important role in our investigation. Precisely, our goal in this article is to give necessary and sufficient optimality conditions for problem (S ). Normal cones, subdifferentials and min-max problems are used to express some of these optimality conditions. In particular, under appropriate assumptions and a new constraint qualification, we provide a necessary and sufficient optimality condition which reduces the problem (S ) to a min-max problem constrained with compact convex linked constraints. We note that these optimality conditions are new and do not use differentiability assumptions. For papers dealing with optimality conditions for generalized semi-infinite programming problems, we cite, for example, [START_REF] Hettich | Second order optimality conditions for genaralized semi-infinite programming problems[END_REF][START_REF] Th | Generalized semi-infinite optimization: A first-order optimality conditions and examples[END_REF][START_REF] Kanzi | Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems[END_REF][START_REF] Kanzi | Convex generalized semi-infinite programming problems with constraint sets: Necessary conditions[END_REF][START_REF] Kanzi | Lagrange multiplier rules for non-differentiable DC geneneralized semi-infinite programming problems[END_REF][START_REF] Rückmann | First-order optimality conditions in generalized semiinfinite programming[END_REF][START_REF] Rückmann | Second-order optimality conditions in generalized semiinfinite programming[END_REF][START_REF] Stein | On optimality conditions for generalized semi-infinite programming problems[END_REF][START_REF] Stein | First order optimality conditions for degenerate index sets in generalized semi-infinite programming[END_REF][START_REF] Still | Generalized semi-infinite programming : Theory and methods[END_REF][START_REF] Ye | First-order optimality conditions for generalized semi-infinite programming problems[END_REF][START_REF] Chen | Optimality conditions for nonsmoth generalized semi-infinite programs[END_REF].

This article is organized as follows. In section 2, we recall some fundamental results of convex analysis that we need in the sequel. Section 3 is devoted to some preliminaries. In section 4, we provide necessary and sufficient optimality conditions for the generalized semiinfinite programming problem (S ).

BACKGROUND OF CONVEX ANALYSIS

In this section, we recall some results related to convex analysis that we will use in the sequel.

Definition 2.1. Let h : n -→ be a function. The set dom h = x ∈ n / h(x) < +∞
is called the effective domain of h. The function h is said to be proper if dom h = ∅, and h(x) > -∞, for all x ∈ n .

In the sequel, for a subset A of n , int A and bd A denote, respectively, the interior and the boundary of A.

Proposition 2.1 ( [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF]). Let C be a nonempty convex subset of n with a nonempty interior. Then, C = int C .

Proposition 2.2 ([13]

). Let h : n -→ be a convex function. Assume that there exists x 0 ∈ n such that h(x 0 )<0. Then [START_REF] Rockafellar | Convex Analysis[END_REF]). Let h : n -→ ∪ +∞ be a proper convex function. Assume that int(dom h) is nonempty. Then, h is continuous on int(dom h). Definition 2.2. Let h : n -→ ∪ +∞ be a convex function, x ∈ dom h and x * ∈ n .

1) int x ∈ n /h(x) ≤ 0 = x ∈ n /h(x) < 0 , 2) bd x ∈ n /h(x) ≤ 0 = x ∈ n /h(x) = 0 . Theorem 2.1 ([
1) The vector x * is said to be a subgradient of h at x if

h(x) ≥ h( x)+ < x * , x -x > ∀x ∈ n
The set of all subgradients of h at x, which is denoted by h( x), is called the subdifferential of h at x, that is, the set defined by

h( x) = x * ∈ n /h(x) ≥ h( x)+ < x * , x -x >, ∀x ∈ n When h( x) = ∅, we say that h is subdifferentiable at x. 2) Let ≥ 0. The vector x * is said to be an -subgradient of h at x if h(x) ≥ h( x)+ < x * , x -x > -∀x ∈ n
The set of all -subgradients of h at x, which is denoted by h( x), is called the -subdifferential of h at x, that is, the set defined by

h( x) = x * ∈ n / h(x) ≥ h( x)+ < x * , x -x > -, ∀x ∈ n When = 0, h( x) reduces to h( x).
Then, we have the following results concerning the subdifferential.

Theorem 2.2 ([14]

). Let h : n -→ ∪ +∞ be a proper convex function. Assume that int(dom h) is nonempty. Then, for all x ∈ int(dom h), we have h(x) = ∅.

Theorem 2.3 ([13]

). Let f , g : n → ∪ +∞ be two convex functions. Assume that there exists x 0 ∈ domf ∩ domg such that g is continuous at x 0 . Then, for every x ∈ domf ∩ domg and ≥ 0, we have

(f + g )(x) = 1 , 2 ≥0 1 + 2 = 1 f (x) + 2 g (x)
Definition 2.3. Let C be a nonempty convex subset of n and x ∈ C . The normal cone of C at x, denoted by (C , x) is defined by

(C , x) = x * ∈ n / < x * , x -x >≤ 0, ∀x ∈ C Definition 2.4.
Let C be a nonempty convex subset of n and x ∈ C . Let ≥ 0. The set of -normal directions to C at x, denoted by (C , x) is defined by

(C , x) = x * ∈ n / < x * , x -x >≤ , ∀x ∈ C When = 0, then (C , x) reduces to (C , x).
Definition 2.5. Let A be a subset of n . The indicator function of A denoted by A is the function defined on n by [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF]). Let C be a closed convex subset of n . Let x ∈ bd C . Then, there exists x * ∈ n \ 0 , such that x * ∈ (C , x).

A (x) = 0 if x ∈ A +∞ if x ∈ A Proposition 2.3 ([

Theorem 2.4 ([13]). Let C and D be two nonempty convex subsets of n . Assume that C

∩ int D = ∅. Let x ∈ C ∩ D. Then C ∩D (x) = C (x) + D (x)
In the sequel, for a function h : n -→ and ∈ , (h) will denote the lower level set of h at , that is,

(h) = y ∈ n /h(y) ≤
Then, we have the following results.

Theorem 2.5 ([13]). Let h :

n -→ be a convex function. Let x ∈ n such that 0 h(x). Then h(x) (h), x = + h(x)
where

+ h(x) = x * / ∈ + , x * ∈ h(x) .
Theorem 2.6 ( [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF]). Let h : n -→ be a convex function and ∈ . Assume that there exists x ∈ n such that h( x) < . Then, for any x ∈ bd( (h)), we have

( (h), x) = ≥0 ( h) (x)
Theorem 2.7 ( [START_REF] Hiriart-Urruty | From convex optimization to nonconvex optimization. Part I: Necessary and sufficient conditions for global optimality[END_REF]). Consider the following convex maximization problem

( ) max x∈ X h(x),
where h : n → is a convex function and X is a closed convex subset of n . Let x ∈ X be a local maximum of ( ). Then h( x) ⊂ ( X , x)

PRELIMINARIES

In this section, we give some preliminary results that will be useful for our study. For the convenience of the reader, let us first recall the following definition.

Definition 3.1. Consider the following minimization problem

( ) min x∈ X ĝ (x)≥0 ĥ(x),
where ĥ : p → is a function, ĝ : p → is a convex function and X is a nonempty subset of p . The constraint g (x) ≥ 0 is called a reverse convex constraint and the problem ( ) is called a problem with a reverse convex constraint. It follows that the complement of the set x ∈ p /g (x) ≥ 0 is open and convex. If, moreover, ĥ and X are convex,

( ) is called a reverse convex problem. The constraint g (x) ≥ 0 is called essential if inf x∈ X ĥ(x) < inf x∈ X ĝ (x)≥0 ĥ(x)
Note that when this property is not satisfied, the problem ( ) is reduced to a convex programming problem.

In the sequel, and under appropriate assumptions, the generalized semi-infinite programming problem (S ) will be viewed as a reverse convex problem. Then, we will make the following assumptions.

(3.1) The set X is convex and compact, (3.2) The functions F is convex on p , (3.3) The functions G is concave on p × q , (3.4) The function g is convex on p × q , (3.5) inf x∈X F (x) < inf(S ), where inf(S ) denotes the infimal value of problem (S ), (3.6) There exists a convex compact subset Z of q , such that Y (x) ⊂ Z , for any x ∈ X .

For (x, y)

∈ p × q , set f (x, y) = -G (x, y) and v(x) = inf y∈Y (x) f (x, y)
Then, the problem (S ) is written as

(S ) min x∈X v(x)≥0 F (x, y) Remark 3.1. Let Assumptions (3.1)-(3.5) hold. Assumptions (3.
3) and (3.4) imply that the marginal function v( ) is convex, and Assumption (3.5) implies that there exists x ∈ X verifying F ( x) < inf(S ) and v( x) < 0 So that, in this case the constraint v(x) ≥ 0 is essential. Furthermore, (S ) is a reverse convex problem. This leads to the following definition. Definition 3.2. Assume that X is convex, F and g are convex functions on p and p × q , respectively, and G is concave on p × q . We call the problem (S ) a reverse convex generalized semi-infinite programming problem. Consider the following minimization problem

( ) min x∈X v(x)=0 F (x)
Then, we have the following result. Proof. Let x ∈ X be the point given in Remark 3.1 which satisfies

F ( x) < inf(S ) and v( x) < 0 (1)
i) Let x be a solution of problem (S ). Note that such a point exists according to Remark 3.2. Let us show that v( x) = 0. Assume that v( x) > 0. Then, x = x, and from the continuity of the function v( ), there exists x ∈

x, x ,

x = t x + (1 -t ) x, t ∈ 0, 1[, verifying v( x) = 0.
Hence, x is a feasible point of (S ). Then, from the convexity of F , we have

F ( x) ≤ tF ( x) + (1 -t )F ( x) < F ( x),
which contradicts the optimality of x to the problem (S ). To show that x solves ( ), let x be a feasible point of problem ( ). Then, x is a feasible point of (S ). Hence,

F ( x) ≤ F (x)
So that x solves ( ).

Conversely, let x be a solution of ( ). Then v( x) = 0. Hence,

inf(S ) ≤ F ( x) (2)
Let x be a feasible point of (S ). We distinguish the following cases.

1) Assume that v(x) = 0. Hence, x is a feasible point of problem ( ). So that F ( x) ≤ F (x).
2) Assume that v(x) > 0. Using [START_REF] Hettich | Second order optimality conditions for genaralized semi-infinite programming problems[END_REF] and that the marginal function v( ) is continuous on p , it follows that there exists

x * ∈ x, x , x * = t x + (1 -t )x, t ∈ 0, 1[ verifying v(x * ) = 0. Since X is convex, then x * ∈ X . So that x * is a feasible point of ( ). It follows that F ( x) ≤ F (x * ) (3)
Assume that F ( x) > F (x). From the convexity of F , we have

F (x * ) ≤ tF ( x) + (1 -t )F (x) < t inf(S ) + (1 -t )F ( x)
Using (2), we obtain

F (x * ) < F ( x)
which contradicts [START_REF] Kanzi | Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems[END_REF]. It follows that

F ( x) ≤ F (x)
Therefore, from the two cases, we deduce that x is a solution of (S ).

ii) We have

x ∈ X /v(x) = 0 ⊂ x ∈ X /v(x) ≥ 0 So that inf(S ) ≤ inf( )
Let x 1 and x 2 be solutions to problems (S ) and ( ), respectively. From the above case i), we have v(x 1 ) = 0. So that, x 1 is a feasible point of ( ). It follows that

F (x 2 ) = inf( ) ≤ F (x 1 ) = inf(S ),
where the inequality follows from the feasibility of x 1 to problem ( ). We deduce that inf(S ) = inf( ).

Remark 3.3. Note that a necessary condition for a feasible point x of (S ) to be optimal is that v(x) = 0 [see the proof of i) of Proposition 3.1].

OPTIMALITY CONDITIONS

In this section, we provide necessary and sufficient optimality conditions for the generalized semi-infinite programming problem (S ). Some of these optimality conditions are established via stability results.

i) v( x) = 0, ii) X ∩ int( F ( x) (F )) ⊂ X ∩ int( v( x) (v)).
Proof. Let x be the point given in Remark 3.1 that satisfies F ( x) < inf(S ) and v( x) < 0 ( ⇒) Assume that x is a solution of (S ). Then, v( x) = 0 (see Remark 3.3). We have

F ( x) < inf(S ) = F ( x) and v( x) < 0 = v( x)
With the above two strict inequalities and the convexity of F and v, we deduce that

int( F ( x) (F )) = x ∈ p /F (x) < F ( x) and int( v( x) (v)) = x ∈ p /v(x) < v( x) = x ∈ p /v(x) < 0 Assume that X ∩ int( F ( x) (F )) is not a subset of X ∩ int( v( x) (v)). Then, there exists x ∈ X such that F ( x) < F ( x), but v( x) ≥ v( x) = 0 that is, x ∈ int( v( x) (v)).
Hence, x is a feasible point of (S ). This contradicts the optimality of x.

(⇐ ) Let the conditions i) and ii) be satisfied. Assume that there exists x ∈ X such that v(x) ≥ 0 and

F (x) < F ( x) (4)
that is, x is not a solution of (S ). Then we have x ∈ X ∩ int( F ( x) (F )).

Property ii) implies that

v(x) < v( x)
Since from i) we have v( x) = 0, it follows that v(x) < 0, which contradicts the first inequality in (4). So that x is a solution of (S ).

From Theorem 4.1 we deduce the following necessary optimality condition expressed in terms of normal cones and subdifferentials.

Corollary 4.1. Let Assumptions (3.1)-(3.6) hold. Let x be a feasible point of problem (S ).

Assume that x is a solution of (S ). Then, v( x) = 0 and for any ≥ 0, we have

1 , 2 ≥0 1 + 2 = 1 (X , x) + ≥0 2 ( v)( x) ⊂ 1 , 2 ≥0 1 + 2 = 1 (X , x) + ≥0 2 ( v)( x)
Proof. Since x solves (S ), it follows from Theorem 4.1 that v( x) = 0 and

X ∩ int( F ( x) (F )) ⊂ X ∩ int( v( x) (v)) Then intX ∩ int( F ( x) (F )) ⊂ X ∩ int( F ( x) (F )) ⊂ X ∩ int( v( x) (v)) ⊂ X ∩ v( x) (v) = X ∩ v( x) (v) (5)
where the above equality follows from the closedness of the sets X and

v( x) (v). Moreover, intX ∩ int( F ( x) (F )) = int X ∩ F ( x) (F ) = X ∩ F ( x) (F ) = X ∩ F ( x) (F )
where the above second equality follows from the convexity of the set X ∩ F ( x) (F ) (see Proposition 2.1). Therefore, from ( 5) we obtain

X ∩ F ( x) (F ) ⊂ X ∩ v( x) (v)
So that, for any ≥ 0, we have

X ∩ v( x) (v) ⊂ X ∩ F ( x) (F ) (6)
Let x ∈ X be the point given in Remark 3.1. Then, x satisfies

F ( x) < F ( x) and v( x) < v( x) So that X ∩ int( F ( x) (F )) = ∅ and X ∩ int( v( x) (v)) = ∅ Then, we have dom X ∩ int dom F ( x) (F ) = ∅ and dom X ∩ int dom v( x) (v) = ∅ Let ( ) = x ∈ X /F (x) ≤ and (S ) = x ∈ X /v(x) ≥
be, respectively, the feasible sets of problems ( ) and (S ) respectively. Note that for = 0, we obtain the problem (S ).

The following Propositions 4.1 and 4.2 give stability results for problems ( ) and (S ), respectively. Their proofs are an adaptation of those given in [START_REF] Tuy | Convex Programs with additional reverse convex constraint[END_REF]. These stability results allow us to establish a necessary and sufficient optimality condition that reduces the problem (S ) to a minmax problem. Then, in order to provide the main result of this section, we need first to establish some preliminary results.

lim m→+∞ sup( m ) = sup( ) Proof. Let k → 0 + , k ∈ . For k , there exists x k ∈ X , such that F (x k ) ≤ and v(x k ) > sup( ) -k
We distinguish the following cases.

Case 1. Assume that there exists k 0 ∈ , such that

F (x k ) = ∀ k ∈ , k ≥ k 0
Then, since is not a local minimum of F over X , for 1 p , there exists

x k,p ∈ B(x k , 1 p ) ∩ X , such that F (x k,p ) < F (x k ) = ∀ k ≥ k 0
We have x k,p → x k , as p → +∞. Then, from the continuity of F as a finite convex function, we have F (x k,p ) → F (x k ), as p → +∞. Moreover, m → , as m → +∞, and m < , ∀ m ∈ . Then, there exists m 0 ∈ , such that

F (x k,p ) < m , ∀ m ≥ m 0 Since x k,p is a feasible point of problem ( m ), m ≥ m 0 , we have sup( m ) ≥ v(x k,p ) m ≥ m 0 Then lim inf m→+∞ sup( m ) ≥ v(x k,p ) Since v( ) is lower semi-continuous on p , then lim inf m→+∞ sup( m ) ≥ lim inf p→+∞ v(x k,p ) ≥ v(x k ) ≥ sup( ) -k Letting k → +∞, we obtain lim inf m→+∞ sup( m ) ≥ sup( ) (7)
On the other hand, for every m ∈ , we have ( m ) ⊂ ( ), and, hence,

sup( m ) ≤ sup( ) So that lim sup m→+∞ sup( m ) ≤ sup( ) (8)
From ( 7) and ( 8), we deduce that lim m→+∞ sup( m ) = sup( ) Case 2. Assume that there exists an infinite subset of such that

F (x k ) = ∀ k ∈ So that F (x k ) < ∀ k ∈
Then, for all k ∈ , we have

F (x k ) < m for large m It follows from the feasibility of x k to problem ( m ) that sup( m ) ≥ v(x k ) > sup( ) -k Then lim inf m→+∞ sup( m ) ≥ sup( ) -k Letting k → +∞, k ∈ , we obtain lim inf m→+∞ sup( m ) ≥ lim k→+∞ k∈ (sup( ) -k ) = sup( ) (9)
On the other hand, we have

sup( ) ≥ sup( m ) Then sup( ) ≥ lim sup m→+∞ sup( m ) (10)
From ( 9) and ( 10), we obtain

lim m→+∞ sup( m ) = sup( )
The following theorem provides a necessary optimality condition for (S ).

< , ∀ m ∈ . Let x ∈ X such that F (x) ≤ m . Then v(x) < 0 (11) Otherwise v(x) ≥ 0. So that m < = F ( x) = inf(S ) ≤ F (x) ≤ m
which gives a contradiction. Then, from (11), we have

sup x∈X F (x)≤ m v(x) = sup( m ) ≤ 0 Proposition 4.1 implies that lim m→+∞ sup( m ) = sup( ) ≤ 0 Since v( x) = 0 and x is a feasible point of problem ( ), it follows that sup( ) = sup x∈X F (x)≤F ( x) v(x) = 0 = sup x∈X F (x)≤F ( x) inf y∈Y (x) f (x, y) with f (x, y) = -G (x, y). So that inf x∈X F (x)≤F ( x) sup y∈ q g (x,y)≤0 G (x, y) = 0
We consider the following constraint qualification: (4.1) For every x ∈ X verifying v(x) = 0, there exist x * ∈ v(x) and x ∈ X , such that x * , xx > 0.

lim m→+∞ inf(S m ) = inf(S ) Proof. Let k → 0 + , k ∈ . For k , there exists x k ∈ X such that v(x k ) ≥ 0 and F (x k ) < inf(S ) + k
We distinguish the following cases.

Case 1. Assume that there exists k 0 ∈ , such that v(x k ) = 0 ∀ k ≥ k 0 Assumption (4.1) means that for every x ∈ X such that v(x) = 0, v(x) is not a subset of (X , x). So that 0 is not a local maximum of v( ) over X (Theorem 2.7). Then, for 1 p , p ∈ * , there exists

x k,p ∈ B x k , 1 p ∩ X , such that v(x k,p ) > v(x k ) = 0
Then, there exists m 0 ∈ , such that

v(x k,p ) > m ∀ m ≥ m 0 Since x k,p is feasible for (S m ), m ≥ m 0 , then inf(S m ) ≤ F (x k,p ) So that lim sup m→+∞ inf(S m ) ≤ F (x k,p )
Since F is upper semi-continuous on p and x k,p → x k , as p → +∞, then lim sup

m→+∞ inf(S m ) ≤ lim sup p→+∞ F (x k,p ) ≤ F (x k ) < inf(S ) + k Letting k → +∞, we obtain lim sup m→+∞ inf(S m ) ≤ inf(S ) (12)
On the other hand, we have

(S m ) ⊂ x ∈ p / x ∈ X , v(x) ≥ 0 Then inf(S ) ≤ inf(S m ) and inf(S ) ≤ lim inf m→+∞ inf(S m ) (13)
From ( 12) and ( 13), we deduce that

lim m→+∞ inf( m ) = inf(S )
Case 2. Assume that there exists an infinite subset of such that

v(x k ) = 0 ∀ k ∈ So that v(x k ) > 0 ∀ k ∈
Since m → 0 + , there exists m 0 ∈ such that for all k ∈ , we have

v(x k ) > m ∀ m ≥ m 0 Hence, x k is a feasible point for (S m ), m ≥ m 0 . Then inf(S m ) ≤ F (x k ) < inf(S ) + k So that lim sup m→+∞ inf(S m ) ≤ F (x k ) < inf(S ) + k Letting k to +∞, k ∈ , we obtain lim sup m→+∞ inf(S m ) ≤ lim k→+∞ k∈ (inf(S ) + k ) = inf(S ) (14)
On the other hand, we have

inf(S ) ≤ inf(S m ) So that inf(S ) ≤ lim inf m→+∞ inf(S m ) (15)
Hence, from ( 14) and ( 15), we obtain

lim m→+∞ inf(S m ) = inf(S )
The following theorem gives a sufficient optimality condition. The proof is based on the use of the stability of problem (S ) under perturbation (Proposition 4.2).

Proof. Let

m → 0, with m > 0, ∀ m ∈ . Let x ∈ X such that v(x) ≥ m , ∀ m ∈ . Then F (x) > F ( x) (16)
Otherwise

, F (x) ≤ F ( x). So that m ≤ v(x) ≤ sup u∈X F (u)≤F ( x) v(u) = 0 = v( x) < m
which gives a contradiction. Then, property [START_REF] Tuy | Convex Programs with additional reverse convex constraint[END_REF]

implies that inf(S m ) = inf x∈X v(x)≥ m F (x) ≥ F ( x) It follows from Proposition 4.2 that lim m→+∞ inf(S m ) = inf(S ) ≥ F ( x)
So that F ( x) = inf(S ). Hence, x solves (S ).

The following theorem gives a necessary and sufficient optimality condition that reduces the problem (S ) to a min-max problem with compact convex linked constraints.

4.1. Let X = -4, 4 , F : → , G : 2 → , g = (g 1 , g 2 ):
2 → 2 be the functions defined by

F (x) = x 2 + 1 G (x, y) = -3x 2 -y 2 + 1 g 1 (x, y) = -x -y g 2 (x, y) = y -x For all x ∈ -4, 4 , we have Y (x) = -x, x ⊂ -
(x 2 + 1) = 1 < min x∈[-4,4] -3x 2 -y 2 +1≤0, ∀ y∈[-x,x] (x 2 + 1) = 4 3
Hence, Assumption (3.5) is satisfied. Let us verify Assumption (4.1). We have

v(x) = 3x 2 -1 v(x) = v (x) = 6x x ∈ [-4, 4]/v(x) = 0 = - 1 √ 3 , 1 √ 3 v - 1 √ 3 = -2 √ 3 and v 1 √ 3 = 2 √ 3 • For x = 1 √ 3 , let x * = 2 √ 3 ∈ v 1

CONCLUSION

Our investigation in this article concerned a class of nonsmooth generalized semi-infinite programming problems whose feasible sets are represented by a reverse convex constraint. So the use of reverse convex problems played an important role to establish our results. Then, for problem (S ), under appropriate assumptions, we have given necessary and sufficient optimality conditions. These optimality conditions are new and do not use differentiability assumptions. Normal cones, subdifferentials, and max-min problems are the main tools used to express these optimality conditions. In particular, using a new constraint qualification (Assumption (4.1)), we have provided a necessary and sufficient optimality condition which reduces (S ) to a min-max problem with compact convex linked constraints. Therefore, such an optimality condition provides an alternative to solve the considered class of generalized semi-infinite programming problems via min-max problems with linked constraints.

Remark 3 . 2 .

 32 Let Assumptions (3.3),(3.4), and (3.6) hold. Then, the marginal function v( ) is convex and finite valued. Hence, it is a continuous function on p (Theorem 2.1). If, moreover, Assumptions (3.1) and (3.2) are satisfied, then, the problem (S ) admits at least one solution.

Proposition 3 . 1 .

 31 Let Assumptions (3.1)-(3.6) hold. Then, the problems (S ) and ( ) are equivalent in the following sense i) (S ) and ( ) have the same set of solutions, ii) inf(S ) = inf( ).

Theorem 4 . 1 .

 41 (Necessary and Sufficient Optimality Conditions) Let Assumptions (3.1)-(3.6) hold. Let x be a feasible point of problem (S ). Then, x is a solution of (S ) if and only if

Proposition 4 . 1 .

 41 Let ∈ . Assume that Assumptions (3.1)-(3.4) and(3.6) hold, and that is not a local minimum of F over X . Then, for any sequence m → , as m → +∞, with m < , ∀ m ∈ , we have

Theorem 4 . 2 .

 42 Assume that Assumptions (3.1)-(3.6) are satisfied. Assume that x is a solution of (S ). Then, v( x) = 0 and inf x∈X F (x)≤F ( x) sup y∈ q g (x,y)≤0 G (x, y) = 0 ( x) Proof. The condition v( x) = 0 follows from Theorem 4.1. Let = F ( x), and m → , as m → +∞, with m

Remark 4 . 1 .

 41 Assumption (4.1) is equivalent to say that for every x ∈ X verifying v(x) = 0, we have v(x) ⊂ (X , x). In other terms, if denotes the set of solutions to the problem max x∈X v(x) we have x ∈ X /v(x) = 0 ∩ = ∅ Proposition 4.2. Let Assumption (3.1)-(3.6) and (4.1) hold. Let m → 0 + , as m → +∞, with m > 0, ∀ m ∈ . Then

Theorem 4 . 3 .

 43 Let Assumptions (3.1)-(3.6) and (4.1) hold. Let x be a feasible point of (S ). Assume that v( x) = 0 and x satisfies the condition ( x) given in Theorem 4.2. Then, x solves (S ).

Theorem 4 . 4 .

 44 Let Assumptions (3.1)-(3.6) and (4.1) hold. Let x be a feasible point of (S ). Then, x solves (S ) if and only ifi) Then, v( x) = 0, ii) inf x∈X F (x)≤F ( x)sup y∈ q g (x,y)≤0 G (x, y) = 0.Proof. Use Theorems 4.2 and 4.3.For illustration, let us give the following simple example.

Example

√ 3 , 3 > 0 • 1 √ 3 , 2 √ 3 ∈ v - 1 √ 3 , 1 √ 3 and x = 1 √ 3 3 ( 1 -Therefore, - 1 √ 3 and 1 √ 3

 3301323131313311313 and x = 4 ∈ X . Then x * x -1 √ For x =let x * =and x = -4 ∈ X . Then x (4.1) is satisfied. Let us find the solutions of problem (S ) via the optimality conditions. For this, let us apply Theorem 4.4. Let x be a feasible point of (S ). Then, x solves (S ) if and only if v( x) = 0 and inf x∈X F (x)≤F ( x) sup y∈ g (x,y)≤0 G (x, y) = 0 The equation v( x) = 0, gives x = -Replacing the functions F , G , and g by their expressions, we get inf x∈X F (x)≤F ( x) y∈[-x,x](-3x 2y 2 + 1) = 1 -3x 2 ) = 0 are solutions of (S ).

On the other hand, we have

Using Theorems 2.1 and 2.3, we obtain

On the other hand, since int(

Hence,

By similar calculation and arguments, we also have

Then, the result follows from the inclusion in [START_REF] Rückmann | First-order optimality conditions in generalized semiinfinite programming[END_REF].

In the remainder of this section, we will give optimality conditions involving stability results. For ∈ , we consider the following parameterized maximization problem

and for ∈ , we associate to the generalized semi-infinite programming problem (S ) the following parameterized minimization problem (S ) min