Elarbi Chatir

Martial Boggio-Pasqua

Frederique Loiseau

Christian Philouze

Guy Royal

Saioa Cobo
email: saioa.cobo@univ-grenoble-alpes.fr

Dr M B-P

Synthesis of Redox-Active Photochromic Phenanthrene Derivatives

A phenanthrene unit has been functionalized by several methylthiophene units in order to bring it a photochromic behavior. These compounds were characterized by NMR, absorption and emission spectroscopies, theoretical calculations as well as cyclic voltammetry. The association of a phenanthrene group with a photochromic center could open the door to a new generation of organic field-effect transistors.

Introduction

Polycyclic aromatic hydrocarbons (PAHs) have focused large interest in the last decade because of their extensive applications in optoelectronic devices, as opto-transistors or in organic fieldeffect transistors. [1][2][3] Since several years the diversifying of the PAH structures with the introduction of hetero-elements has emerged as a priority for the modulation of the electronic properties. This strategy has been notably applied with the introduction of sulfur element through thienyl unit. [4][5][6][7][8][9] Indeed, the latest is known to show unique electronic, optical and redox properties. [10] Moreover, the polarizability of S atoms leads to a stabilization of the conjugated molecules and to excellent charge transport properties, essential for applications in molecular electronics. [5] Furthermore, thienyl units are the main constituents in the skeleton of the dithienylethene (DTE) photochromic molecules. DTE is a non-linear compound containing two thiophene groups connected by an ethene bridge. This molecule undergoes a photochemically and electrochemically reversible 6πelectrocyclization between two isomers, namely a low conjugated open form and a high conjugated closed form (Scheme 1). [11] Several studies have been devoted to the modification of the simple ethene bridge, [12][13][14][15] the most popular and successful being the perfluorocyclopentene derivatives. [11,16,17] Over the last decade, significant efforts have been made towards the introduction of new aromatic bridges based on PAH instead of the ethene bridge in the skeleton of DTE molecules. However, to date, only molecules involving phenanthroline and phenanthrene can be included in the category of photochromic PAH.

Phenanthroline-based photochromic materials have been widely used as an efficient coordinating unit in order to build up complexes exhibiting particular fluorescent [18] or magnetic properties [19] depending on the photo-isomer. On the contrary, examples concerning the phenanthrene unit are scarce. Feringa et al. [20] described a photochromic phenanthrene derivative in which, for the first time, the photochemistry of individual atropoisomers has been studied. This phenomenon has been possible due to the higher energy barrier of the conformations in the phenanthrene derivatives induced by the restricted rotation of the thienyl groups compared to the cyclopentene derivatives. Later, the modification of the phenanthrene entity with coordinating units such as pyridine opened the door to the coordination chemistry field. Thus, Benedict et al. [21,22] reported the synthesis and photochromic properties of a molecular organic framework. Recently, Ma et al. [23] [23] , synthetized two rhenium compounds from a photochromic ligand in which the rhenium metal center is linked to the phenanthrene through a coordinating unit. However, to date, all investigations involving a phenanthrene unit in the photochromic skeleton of the compounds have been focused on the study of the photochromic properties neglecting Scheme 1. Schematic representation of the photochemical isomerization of a dithienylethene.

the study and the understanding of the electrochemical properties, that are essential for the application of these compounds in the field of switchable molecular electronics. Thus, in order to go a step further, we focus in this paper on the synthesis, photochemical and electrochemical properties of four PAH-DTE derivatives. These compounds contain phenanthrene units as a PAH platform bearing pyridine or N-methyl pyridinium units which can be appended to the thienyl units (6 and 7 2+ ) or to the phenanthrene bridge (8 and 9 2+ ). The previously synthetized compound 8 by Ma et al. [23] is also reinvestigated. In addition, theoretical calculations based on density functional theory (DFT) and its time-dependent version (TD-DFT) have been performed on selected compounds in order to rationalize the experimental observations.

Results and Discussion

Synthesis and characterisation

The target photochromes 6o and 8o and their corresponding quaternized analogues 7o 2+ and 9o 2+ were prepared following the synthetic route summarized in scheme 2 (o refers to the open form). The synthesis starts with the Friedel-Crafts acylation of 2chloro-5-methylthiophene with the diacid chloride of diphenic acid generated in situ. The resulting diketone is then cyclized under McMurry coupling conditions to yield the dichloride derivative. At this step, the intermediate is subjected to a lithium-halogen exchange followed by a Suzuki-Miyaura coupling reaction to yield 6o or directly with the same cross-coupling reaction in the presence of 4-pyridylboronic acid and tetrakistriphenylphosphine palladium (0) to yield 8o as a yellow solid. The bis-N-methylations are achieved using an excess of methyl iodide, and the crude reaction product was subjected to an anion exchange procedure to afford the targeted pyridinium salts 7o 2+ and 9o 2+ isolated as a yellow powder. All of the compounds were characterized by mass spectrometry and NMR spectroscopy (see the Experimental Section and the Supporting Information). Compounds 6o and 8o crystallize in the monoclinic system C2/c and P21/c, respectively, with DTE is in its open form. The distances between the two reactive carbon atoms are 4.698 and 4.368 Å for 6o and 8o respectively. In both cases the thienyl groups lie in an antiparallel conformation and adopt a perpendicular arrangement with respect to the phenanthrene moiety, with dihedral angles of 90 and 115°, respectively. In the structure 6o the pyridine units are in nearly coplanar conformation with respect to thiophene in which the dihedral angle of the pyridine rings with respect to the central thiophene ring is 15.1°. In the structure of 8o the pyridine units exhibit dihedral angles of 32.7° and 49.9° with respect to the phenanthrene group. These two non-cationic structures are stabilized with several intermolecular interactions. 6o shows a packed structure with two kinds on interactions i) a pstacking morphology with a measured p-p distance of 3.1 Å between the pyridine groups (Figure 1a) and ii) Van der Waals interactions between the phenanthrene and the internal methyl of the thienyl counterpart (3.8 Å). These interactions induce a perfect alignment of the phenanthrene bridge which can be seen when looking down the b axis. Contrariwise, on the packing of the structure 8o, only Van der Waals interactions can be observed between the pyridine and the phenanthrene units. The cationic 7o 2+ and 9o 2+ structures crystallize in Pcnb and P21/c orthorhombic system, respectively. Their unit cells show the DTE cation with two PF6 -counterions. Intermolecularly, 7o 2+ possess a 1D-lamelar stacking morphology with a measured p-p distance of 3.3 Å (Figure 1b), suggesting a good molecular orbital contact and the possibility to high mobility charge along this axis. [START_REF] Little | The Synthesis of Novel Polycyclic Aromatic Hydrocarbons: The Search for Organic Semiconductor Materials[END_REF] In contrary, no strong intermolecular interaction has been observed for 9o 2+ .

Optical and electrochemical properties

The spectroscopic data found for compounds 6o, 8o, 7o 2+ and 9o 2+ are collected in Table 2. In the 250-800 nm range the absorption spectrum of phenanthrene (10) displays one absorption band at 254 nm attributed to p-p* transitions. This absorption band is bathochromically shifted by 53 and 32 nm in compounds 6o (Figure 2) and 8o (Figure S13b), respectively, in agreement with an extension of the aromatic p-system. The experimental energy gaps are 3.29 and 3.59 eV for 6o and 8o, respectively. As expected from the literature data, the bands observed on the spectrum of 6o and 8o appear further red shifted in the pyridinium substituted derivatives 7o 2+ (Figure S13a) and 9o 2+ (Figure 2 and Table 1), thereby, the lowest energy bands for the 7o 2+ and 9o 2+ compounds are observed around 350-360 nm range (Figures 1 and2). The experimental energy gaps are 2.97 and 2.89 eV for 7o 2+ and 9o 2+ , respectively. Table 1: Spectroscopy data.

[a] not measurable The closing process converts a set of two virtually isolated thiophene subunits into a 6p-electron aromatic system. This process can be easily monitored by UV-vis absorption spectroscopy following the changes occurring in the spectra when samples are submitted to UV irradiation (365 nm). Irradiation of compounds 6o, 8o and 9o 2+ in acetonitrile leads to a fast (~ 60 s) and moderate decrease of the main absorption band located in the UV region and attributed to the open isomers at the expense of new bands growing in the visible region around 550-600 nm attributed to the closed forms. These results stand in sharp contrast with those obtained under the same conditions with 7o 2+ for which no UV-vis spectroscopic changes have been detected even after prolonged irradiation. Nevertheless, a ns-flash photolysis experiment shows the formation of an absorption band in the visible region of the transient absorption spectrum of 7o 2+ , with a maximum centered at 600 nm (Figure S1). This wavelength corresponds to the domain expected for the absorption of the closed form of compound 7. The absorption band decays back to the ground state in 1025 ns (Figure S2), and is therefore attributed to the re-opening process of the unstable form 7c.

The kinetic of the back-conversion for the closed isomers 6c, 8c and 9c 2+ was investigated since the closed forms are not thermally stable. The latter was assessed upon monitoring the changes appearing in the UV-Vis spectra over time at three different temperatures. The rate constants, half-life times and activation energies were calculated assuming a first-order thermal relaxation process. The calculated activation energies are 12 kcal/mol for 6c, and 18 and 19 kcal/mol for 8c and 9c 2+ , respectively, indicating a very low thermal stability for 6c (the half-life times are less than 1 min at 297 K). These activation energies are consistent with the potential energy barriers computed at the DFT level: 10.9, 15.5 and 15.3 kcal/mol for 6c, 8c and 9c 2+ , respectively (Figures S3-S5). Including thermal and entropic corrections, the activation energies are computed at 8.3, 12.3 and 14.4 kcal/mol respectively.

Emission spectra and excited-state lifetimes in acetonitrile solution for the open compounds have been recorded under inert atmosphere at room temperature. All the spectroscopic data related to emission properties are reported in Table 1. Compound 6o exhibits two maxima of emission, centered at 397 and 508 nm. The higher energy band of emission brings up a vibronic structure and is attributed to the radiative deactivation of a p-p* excited state, essentially centered on the phenanthrene moiety. The second part of the emission profile is likely due to a p-stacking phenomenon between the extended flat surfaces of the phenanthrenes. Indeed, the decay of the emission is biexponential, with a short component of 1.7 ns predominant at high energy, and a longer component of 6.9 ns prevalent in the 500 nm region. Moreover, a 10-fold dilution allows to decrease the ratio of this low-energy emission band (Figure 3). The TD-DFT calculation of the vertical fluorescence transition energy for 6o predicts an emission wavelength of 379 nm in good agreement with the experimental observation. It also confirms that the emission is due to a p-p* locally excited state centered on the phenanthrene moiety (Figure S6a). The absence of electronic transition in the 500 nm region corroborates the fact that this emission feature in the visible range is due to aggregation. The corresponding compound bearing 2 pyridine units on the phenanthrene platform, 8o, has no possibility of stacking because of the torsion angle between the planes of the phenanthrene and of the pyridine rings. This results in a monoexponential decay of the p-p* emission with a lifetime of 1.4 ns, centered at 400 nm, red shifted with respect to the one of 6o because of the presence of the additional rings. In the case of the quaternized analogues 7o 2+ and 9o 2+ the shape and energy of emission radically change (see Figure S14). The maxima of emission are red-shifted to 572 and 559 nm respectively, thus displaying substantial Stokes shifts of about 200 nm. In addition, the emission spectra lose their structures and become much wider. This evidences a modification of the nature of the emissive excited state, explained by the presence of the positively-charged pyridiniums that act as strong electron withdrawing subunits and induces the formation of charge transfer excited states. This is further confirmed by the variation of the maximum wavelength of emission as a function of the solvent polarity (Figure S14). The solvatochromism is a characteristic illustrative of a highly dipolar emissive state, such as a charge transfer excited state. Using our TD-DFT protocol, the vertical fluorescence transition energy for 7o 2+ is computed at 2.173 eV, corresponding to an emission wavelength of 571 nm, which is in excellent agreement with the experimental observation. The nature of the emissive S1 state is of clear charge transfer character between the phenanthrene moiety playing the role of the electron donor and the pyridinium groups playing the role of the electron acceptor (Figure S6b). The electrochemical properties of these derivatives were studied by cyclic voltammetry under an inert atmosphere in acetonitrile containing tetra-n-butylammonium perchlorate (TBAP, 0.1 M) as supporting electrolyte. A vitreous carbon disk was used as working electrode. The number of electrons involved in each oxidation or reduction wave were determined by coulometry measurements. The cyclic voltammetry (CV) curves obtained for 7o 2+ and 9o 2+ isomers are shown in Figures 4 and5, compounds 6o and 8o are not redox actives in the +1/-2V range.

The CV curve of 7o 2+ (Figure 4) features a bielectronic irreversible wave at Epc = -1.42 V (the intensity of this signal was compared to the wave obtained in the presence of an equimolar solution of ferrocene as internal standard). During the back scan, two anodic irreversible peaks can be observed at much less negative potential at Epa = -0.73 and -0.68 V. In agreement with prior studies [START_REF] Peters | [END_REF] and on the basis of DFT calculations, these anodic signals are attributed to the oxidation of a substantial amount of the closed isomer (7c) generated in situ at the electrode interface during the forward scan down to -1.5 V. Surprisingly, the observed new redox waves are not reversible as observed when reducing the solution, indicating a chemical and thermal instability of the generated 7c 2+ which immediately generates the open 7o 2+ isomer.

Further insights into the redox behavior of the 7o 2+ /7c couple have been provided by spectro-electrochemical measurements. In situ absorption spectra were recorded over time during the potentiostatic reduction of 7o 2+ (0.1 mM in CH3CN) carried out at Eapp = -1.5 V. Selected UV-vis absorption spectra collected throughout the electrolysis are displayed in Figure 4. These data reveal that the reduction with two electrons leads to the formation of a blue solution characterized by an intense absorption band in the visible region at 567 nm associated to an extension of the conjugation of the compound and attributed to the neutral closed form. The reversibility of the redox processes was checked by reoxidation of the mixture upon setting the potential at -0.65 V. The progressive decrease in intensity of the band at 567 nm, attributed to 7c, for the benefit of the band attributed to the dicationic open form 7o 2+ , at 365 nm is observed. Thus, we can conclude that the 7c 2+ is highly unstable and not observable in the experiment conditions. This electrochemical behavior is corroborated by our DFT results. Upon 2 electron-reduction, 7o 2+ is expected to undergo a ring-closure to form 7c, this species being 10 kcal/mol lower than the biradical species 7o (Figure S7). The change of spectral features going from 7o 2+ to 7c is also in line with the experimental observations (Figure S8): emergence of an intense absorption band around 600 nm and decrease of the intensity of the band around 400 nm associated with a blue-shift and a broadening of this band. Note that the instability of the 7c 2+ is confirmed by our DFT calculations, as the thermal energy barrier to ring-open is computed at only 7.5 kcal/mol (Figure S9). This low ring-opening energy barrier explains why 7c 2+ is not observed upon irradiation of 7o 2+ . From the electrochemistry measurements and UV-vis spectroscopy the energy gap as well as the HOMO (the highest occupied molecular orbital) and LUMO (lowest unoccupied molecular orbital) energy levels of 7o 2+ and 7c have been calculated. The energy gap is of 2.97 (417 nm) and 1.71 (726 nm) eV and the HOMO/LUMO values are -6.352/-3.382 eV and -3.982/-2.272 eV for 7o 2+ and 7c respectively. These results are supported by DFT calculations which provide the following HOMO/LUMO energies -6.149/-2.932 eV and -3.950/-1.631 eV for 7o 2+ and 7c respectively.

The electrochemical behavior of 9o 2+ was also studied by cyclic voltammetry (Figure 5). The CV curve of 9o 2+ features a reversible bielectronic wave at -1.32 V attributed to the pyridinium moieties. Contrariwise to the electrochemical behaviour of 7o 2+ , no wave has been detected during the return scan suggesting that the ringclosure of 9o 2+ cannot be achieved through a redox stimulus. In order to investigate the electrochromic properties of the 9o 2+ compound in depth, spectro-electrochemical measurements were carried out. The absorption spectra were recorded during the potentiostatic reduction of 9o 2+ (0.1 mM in CH3CN) performed at -1.5 V. Selected UV-vis absorption spectra collected throughout the electrolysis are displayed in Figure 5. Starting from a light-yellow solution characterized by a single absorption band at 348 nm in the UV region, the solution becomes dark blue, the UV band disappear and new bands emerge in the visible region (474 and 673 nm). This spectro-electrochemical experiment results combined with the absence of a redox wave on the return scan during the cyclic voltammetry of 9o 2+ suggest that the intense blue color of the solution is due to the reduction of pyridinium units on the 9o 2+ form to afford 9o. Thus, it can be concluded that the closed isomer cannot be formed when the pyridinium units are in the 2 and 7 positions of the phenanthrene.

In order to confirm the formation of the 9o compound the spectroelectrochemical properties of a reference compound in which the phenanthrene bridged two pyridinium units (15 see figure S15) has been investigated. The CV of the reference compound presents a reversible redox wave located at -1.34 V. During the electrochemical reduction at Eapp-1.5 V, the solution goes from yellow to blue, and the maximum of the absorption spectra shifts from 350 to 658 nm. Indicating that the color change can also be induced by the electrochemical reduction of the pyridinium units. These observations are supported by our DFT calculations. Upon 2 electron-reduction, 9o 2+ is predicted to form 9o without formation of the closed form 9c (Scheme 3). Indeed, 9c is located 27 kcal/mol above 9o and involves a potential energy barrier for the thermal ring-closing reaction over 40 kcal/mol (Figure S10). The change of spectral features going from 9o 2+ to 9o (Figure 11) is also in line with the experimental observations (Figure 5): appearance of an absorption band around 700 nm. This band in the red region for 9o is due to the increased conjugation between the pyridinium units and the phenanthrene moiety that become nearly coplanar (Figures S5 andS10). This change of spectral feature is thus only attributed to the reduction of the pyridinium units, which is confirmed by the absorption spectra of the bispyridinium phenanthrene system (15) showing the same spectral changes from the dicationic to the reduced neutral species (Figure S12 can be compared with Figure S15).

Scheme 3. Summary of the electrochemical behavior of 7o 2+ and 9o 2+ .

Conclusion

In conclusion, the different pattern for the substitution of compound 6o and 8o as well as for 7o 2+ and 9o 2+ yields to a drastic difference of photo-and electrochemical behavior. 6o and 8o, compounds bearing pyridine units present a similar photochromic behavior. However, the thermal stability of the closed form is much longer for the compound 8c (more than 30 times) in which the pyridines are diametrically in the opposite positions of the phenanthrene. 7o 2+ and 9o 2+ are electrochemically active compounds. The reduced form of compound 7o 2+ leads to the reduced closed form, 7c, whereas the reduction of compound 9o 2+ inevitably yields to the reduced open form, 9o (Scheme 3). It appears that only the adjacent electron-withdrawing substituents can display a redox closing process. The reduction of substituents at diametrically opposite positions of the phenanthrene are totally independent from the photochromic counterpart as demonstrated by the spectro-electrochemistry experiments and DFT/TD-DFT calculations. Moreover, some of these compounds, notably 6o and 7o 2+ show strong intermolecular interactions, i.e good molecular orbital contact, suggesting a high mobility charge. This strategy, utilizing PAH as bridge can be then widely used for the control of switching processes in DTE derivatives, in order to attempt efficient compounds for applications in molecular electronics.

Experimental Section

All solvents were purchased and used as received except THF that was distillated over sodium/ benzophenone under argon. Water was purified by reverse osmometry with an Elgastat purification system (5 MΩ.cm).

Organic and inorganic reagents used in the procedures described below were purchased on Aldrich, Acros, Fluorochem or TCI Europe and used without further purification. All evaporations were carried out under reduced pressure with a rotatory evaporator, and all organic extract were washed with water and dried with MgSO4. Silica gel (SiGel), used for column chromatography, refers to Merck silica gel, 40-63 μm. 1 H NMR and 13 C NMR spectra were recorded on a Brucker Avanced 500 or 400 MHz spectrometer. Chemicals shifts are calibrated to residual solvent peaks.

Coupling constant values (J) are given in hertz and chemical shifts (δ) in ppm. High-resolution mass spectrometry analyses were conducted using the HRMS, Bruker maXis mass spectrometer and were performed in positive Electrospray Ionisation (ESI+) at the DCM mass facility. Data for single crystal X-Ray diffraction were collected at 200 K on a Bruker AXS Enraf-Nonius Kappa APEXII diffractometer using the Mo-Ka monochromated radiation. Intensity data were corrected for Lorentz and polarization effects with EVAL 14 and for absorption using SADABS.

Structures solutions and refinements were performed with the SHELX softwares implemented by Olex2. All non-hydrogen were refined by full matrix least-squares with anisotropic thermal parameters. Hydrogen atoms were introduced at calculated positions as riding atoms.

Crystallographic structures were drawn with the Mercury 2020.3.0 software. A summary of the data collection and structure refinements is provided in the supplementary information. CCDC 2114398-402 contains the supplementary crystallographic data for this paper (Table S1). These data can be obtained free of charge from The Cambridge Crystallographic Electrochemical measurements (cyclic voltammetry, CV) were conducted under an argon atmosphere with a standard one-compartment, threeelectrode electrochemical cell using a Bio-logic SP300 potentiostat.

Anhydrous CH3CN was used as solvents and tetra-n-butylammonium hexafluorophosphate (TBAPF6, 0.1M) was used as supporting electrolyte. Under argon atmosphere, 9,10-bis(5-chloro-2-methylthiophen-3yl)phenanthrene (500 mg, 1.13 mmol, 1 eq.) was dissolved in a dry THF (10 ml). 2.5 M n-BuLi hexane solution (0.92 ml, 2.48 mmol, 2.05 eq.) was added dropwise to the solution at 0°C. The reaction mixture was allowed to warm to r.t. and stirred for 1 h. Then 2-Isopropoxy-4,4,5,5-tetramethyl- Na2CO3 (81.9 mg, 0.78 mmol, 6 eq.) and Pd(PPh3)4 (9 mg, 0.0065 mmol)

were added under argon flow to a degassed mixture of water (1 mL) and toluene (8mL). The solution was then heated under argon at 100 °C for 24 hours. The reaction was cooled to room temperature, the aqueous phase was then extracted with DCM (2x15 mL). The organic phase was washed with water (10 mL), sat. brine solution (10 mL). The organic phase was dried over Mg2SO4, and then purified by column chromatography (AcOEt/MeOH 1:0 to 9:1) to give the product (8) as a yellow solid (42 mg, 53%). Upon the dropwise addition of an aqueous concentrated KPF6 solution.

The product precipitated as a yellow powder. It was then collected by filtration, washed with water, and dried under vacuum to give 36.8 mg (80%) of the product (9o 2+ ) as a yellow solid.

Computational Section

DFT and TD-DFT calculations were all carried out with the Gaussian16 package [26] Ground-state geometry optimizations were performed with the B3LYP functional [27] along with the 6-31G* basis set [28,29] Vertical absorption transition energies were computed with the PBE0 functional [30] and the more extended 6-311+G** basis set [31,32] The versatile MN15 functional [33] was used for excited-state geometry optimizations and vertical fluorescence transition energy calculations. The solvent effects were accounted for using the integral equation formalism version of the polarizable continuum model (IEFPCM) [34] All calculations were performed in the acetonitrile (e=35.688) solvent. Vertical absorption transition energies were computed using linear-response non-equilibrium solvation.

Calculations of the emission wavelengths were carried out using the more accurate state-specific non-equilibrium approach of Improta and coworkers [35,36] Vibrational harmonic frequency calculations were performed at the optimized geometries to verify the nature of the stationary points (minimum or saddle point) on the potential energy surfaces and to obtain thermal corrections and entropic contributions to compute Gibb's free energies of reaction and activation energies. Open-shell singlet (diradical) species were calculated using broken-symmetry DFT calculations. Spin-projected energies were obtained with an approximate spin-correction procedure to account for the spin contamination. [37,38] Gibb's free energies for these open-shell singlet species were computed by using the spin-projected energies. All the convoluted absorption spectra were obtained using a phenomenological Gaussian broadening characterized by a half-width at half-height of 1500 cm -1 for each vertical transition. All the Cartesian coordinates and energies are provided in Table S2.

Scheme 2 .

 2 Scheme 2. Synthetic pathways leading 6o, 7o 2+ , 8o and 9o 2+ (o refers to the open form).

Figure 1 .

 1 Figure 1. Crystal packing of 6o (a) and 7o 2+ (b) with thermal ellipsoids plotted at the 50% probability level. Hydrogen atoms and PF6 -anions are omitted for clarity. (Full crystallographic data are provided in ESI)

Figure 2 .

 2 Figure 2. UV-vis spectra evolution before (dashed line) and after (black line) irradiation of 6o (a) and 9o 2+ (b) (CH3CN, l = 365 nm, 14 W).

Figure 3 .

 3 Figure 3. Emission spectra of 6o at 2•10 -7 M (full line), 6•10 -8 M (dashed line) and 2•10 -8 M (dotted line) in degassed CH3CN.

Figure 4 .

 4 Figure 4. (a) CV curves recorded for 7o 2+ before (grey line) and after (black line) electrolysis at -1.5 V. (b) Evolution of the UV-vis absorption spectra during the electrolysis of 7o 2+ at Eapp = -1.5 V (initial state, 7o 2+ , dashed line) ([C]= 0.1 mM in 0.1 M TBAP/CH3CN, n: 100 mV•s -1 , VC, Ø = 3 mm, E (V) vs. Ag + /Ag 10 -2 M).

- 1 . 2 Ewe

 12 8 -1.6 -1.4 -1.2 -1.0 -0.8 -0.6 -0.4 -0.2 0.0 0.

Figure 5 .

 5 Figure 5. (a) CV curves recorded for 9o 2+ . (b) Evolution of the UVvis absorption spectra during the electrolysis of 9o 2+ at Eapp = -1.5 V (initial state, 9o 2+ , dashed gray) ([C]= 0.1 mM in 0.1 M TBAP/CH3CN, n: 100 mV•s -1 , VC, Ø = 3 mm, E (V) vs. Ag + /Ag 10 -2 M).

CH-

  Instrument vitreous carbon (3 mm in diameter) working electrodes were used for CV experiments. Electrodes were polished with 1 µm diamond paste (Mecaprex Presi) prior to each recording. Counterelectrode was a platinum wire immerged directly in the solution. A CH-Instrument AgNO3/Ag (10 -2 M + tetra-n-butylammonium perchlorate 10 -1 M in CH3CN) electrode was used as a reference electrode and the potential of the regular ferrocenium / ferrocene (Fc + /Fc) redox couple in acetonitrile is 0.07 V under our experimental conditions. Cyclic voltammetry (CV) curves were recorded at a scan rate of 0.1 V s -1 . An automatic ohmic drop compensation procedure was systematically implemented prior to recording CV data. UV-vis spectroelectrochemical experiments were carried out with a photodiode array UV-vis NIR spectrometer MCS 501 UV-NIR (Carl Zeiss). The light sources were halogen CLH 500 (20 W) and deuterium CLD 500 lamps with an optical fiber 041.002-UV SN 012105 or using an additional 1 mm quartz immersion probe (Hellma) and an automatic shutter. UV-light irradiations have been performed at 366 nm using a hand UV-lamp. Synthetic procedures. 2,7-dibromophenanthrene-9,10-dione, 4,4'-dibromo-[1,1'-biphenyl]-2,2'-dicarboxylic acid, 2-chloro-5methylthiophene, [1,1'-biphenyl]-2,2'-diylbis((5-chloro-2-methylthiophen-3-yl)methanone), (4,4'-dibromo-[1,1'-biphenyl]-2,2'-diyl)bis((5-chloro-2methylthiophen-3-yl)methanone), 9,10-bis(5-chloro-2-methylthiophen-3yl)phenanthrene and 3,3'-(2,7-dibromophenanthrene-9,10-diyl)bis(5chloro-2-methylthiophene) were synthetized following reported procedure (see SI). 9,10-bis(2-methyl-5-(pyridin-4-yl)thiophen-3-yl)phenanthrene (6o):

  methylpyridin-1-ium) hexafluorophosphate (9o 2+ ): To a stirred solution of (4o) (30, mg, 0 .057 mmol) in dry CHCl3 (3 ml) was added methyl iodide (1 mL, large excess). The reaction was stirred at 60°C for 24 h. After cooling, the resulting suspension was filtered. The solid was collected upon filtration and dissolved in a minimum amount of hot CH3OH.

  /www.ccdc.cam.ac.uk/structures ">Access Structures service</url>.

	2114402 (for 7), 2114400 (for 9)</url> contain(s) the supplementary
	crystallographic data for this paper. These data are provided free of charge
	by the joint Cambridge Crystallographic Data Centre and
	Fachinformationszentrum	Karlsruhe	<url	href="
	http:/

Data Centre via www.ccdc.cam.ac.uk/data_request/cif. Deposition Number(s) <url href="https://www.ccdc.cam.ac.uk/services/structures?id=doi:10.1002/ch em.202103755"> 2114398 (for 5a), 2114399 (for 5b), 2114401 (for 6),

  The reaction was stirred at room temperature for 24 h. The resulting suspension was filtered. The solid was collected upon filtration and dissolved in a minimum amount of hot CH3OH. Upon the dropwise addition of an aqueous concentrated KPF6 solution. The product precipitated as a yellow powder. It was then collected by filtration, washed

	with water, and dried under vacuum to give 39 mg (81%) of the product
	(7o 2+ ). as a yellow solid. 1 H NMR (500 MHz, Acetonitrile-d3) δ: 8.96 (d, J =
	8.3 Hz, 2H), 8.38 (d, J = 7.2 Hz, 4H), 7.91 (d, J = 7.1 Hz, 4H), 7.81 (ddd, J
	= 8.3, 6.9, 1.4 Hz, 2H), 7.74 (s, 2H), 7.65 (ddd, J = 8.1, 6.9, 1.1 Hz, 2H),
	7.56 (dd, J = 8.3, 1.3 Hz, 2H), 4.16 (s, 6H), 2.28 (s, 6H). 13 C NMR (125
	MHz, Acetonitrile-d3) δ: 149.40, 147.59, 146.02, 140.51, 134.61, 134.26,
	132.88, 131.76, 131.41, 128.73, 128.68, 127.67, 124.28, 122.65, 27.62,
	15.29. HRMS (ESI) m/z: Calc. for [M+2H] 2+ C36H30N2S2 277.09197. Found.
	277.092001.
	4,4'-(9,10-bis(5-chloro-2-methylthiophen-3-yl)phenanthrene-2,7-
	diyl)dipyridine (8o): In a 100 mL Schlenk tube 3,3'-(2,7-
	dibromophenanthrene-9,10-diyl)bis(5-chloro-2-methylthiophene) (80 mg,
	0.13 mmol, 1 eq.), 4-pyridyl boronic acid (36.2 mg, 0.29 mmol, 2.2 eq.),
	1,3,2-dioxaborolane (0.56 ml, 2.54 mmol, 2.24 eq.) was added and the
	reaction was stirred during 1 h at r.t. Degassed aq. 3 M Na2CO3 (2.26 mL,
	6.78 mmol, 6 eq.), Pd(PPh3)4 (59 mg, 0.056 mmol, 5% mmol) and the 4-
	bromopyridine (446.35 mg, 2.82 mmol, 2.5 eq.) were added and the
	mixture was heated at reflux for 12 h. The crude was then extracted with
	Et2O (3 x 50 ml), dried over Na2SO4 and the solvents were evaporated.
	Purification by chromatography on silica gel using the AcOEt/MeOH
	(100% to 9 :1) afford 380 mg (65%) of the product (6o) as a yellow solid. 1 H
	NMR (500 MHz, CDCl3-d) δ: 8.84 (d, J = 8.3 Hz, 2H), 8.53 (d, J = 6.3 Hz,
	4H), 7.75 -7.70 (m, 2H), 7.67 -7.61 (m, 2H), 7.61 -7.56 (m, 2H), 7.32 (d,
	J = 6.3 Hz, 4H), 7.19 (s, 2H), 2.20 (s, 6H). 13 C NMR (125 MHz, Chloroform-

d) δ: 150.27, 141.59, 138.82, 137.90, 136.93, 132.71, 131.37, 130.50, 127.73, 127.33, 127.22, 127.11, 122.99, 119.45, 14.73. HRMS (ESI) m/z: Calc. for C34H25S2 + 525.14537. Found. 525.14362.

4,4'-(phenanthrene-9,10-diylbis(5-methylthiophene-4,2-diyl))bis(1methylpyridin-1-ium) hexafluorophosphate (7o 2+

). To a solution of (6o) (30, mg, 0.057 mmol) in dry DCM (3 ml) was added methyl iodide (1 mL, large excess).

  1 H NMR (500 MHz, Acetonitrile-d3) δ: 9.18 (d, J = 10 Hz, 2H), 8.65 (d, J = 6.4 Hz, 4H), 8.29 -8.24 (m, 6H), 8.07 (dd, J = 10.8, 2.1 Hz, 2H), 6.81 (s, 1H), 6.73 (s, 1H), 4.31 (s, 6H), 2.11 (s, 3H), 2.06 (s, 3H). 13 C NMR (125 MHz, Acetonitrile-d3) δ: 156.27, 146.27, 137.37, 135.20, 135.07, 134.84, 134.66, 133.25, 133.21, 132.59, 130.23, 128.86, 127.94, 127.81, 126.55, 126.24, 48.53, 14.35. HRMS (ESI) m/z: Calc. for [M] 2+ C36H28N2Cl2S2 2+ 311.05300 Found.

	311.0561.

Acknowledgements

This work was granted access to the HPC resources of CALMIP supercomputing center under the allocation 2021- [12158].


Debabrota Basu

Ambrym Maillard
email: odalric.maillard@inria.fr

Timothée Mathieu
email: timothee.mathieu@

Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm

Keywords: Unbounded corruption, Heavy-tail distributions, Huber's estimator, Regret bounds i ∆

In this paper, we study the stochastic bandits problem with k unknown heavy-tailed and corrupted reward distributions or arms with time-invariant corruption distributions. At each iteration, the player chooses an arm. Given the arm, the environment returns an uncorrupted reward with probability 1-ε and an arbitrarily corrupted reward with probability ε. In our setting, the uncorrupted reward might be heavy-tailed and the corrupted reward might be unbounded. We prove a lower bound on the regret indicating that the corrupted and heavy-tailed bandits are strictly harder than uncorrupted or light-tailed bandits. We observe that the environments can be categorised into hardness regimes depending on the suboptimality gap ∆, variance σ, and corruption proportion ϵ. Following this, we design a UCB-type algorithm, namely HuberUCB, that leverages Huber's estimator for robust mean estimation. HuberUCB leads to tight upper bounds on regret in the proposed corrupted and heavy-tailed setting. To derive the upper bound, we prove a novel concentration inequality for Huber's estimator, which might be of independent interest.

Introduction

In this paper, we consider the problem of sequential decision making where the player has incomplete information about a finite number of decisions and the decisions generate corrupted returns. Specifically, we are interested in the problem of Multi-armed Bandits in a corrupted setting, or in short Corrupted Bandits, in which the player is presented with k> 0 arms corresponding to k unknown probability distributions. At each iteration t ∈ {1, 2, . . .}, the player selects an arm and observes a sample, called reward, generated independently from the corresponding probability distribution. In Corrupted Bandits, the observed reward is corrupted by some unknown adversary or nature. The corruption might also differ from arm to arm. In order to model the corrupted rewards, we consider that the rewards of an arm correspond to a possibly heavy-tailed (with only a finite variance) and corrupted distribution instead of a well-behaved bounded or sub-Gaussian reward commonly found in literature (cite). By corrupted rewards we mean that during the experiment, the environment may randomly generate a reward that is arbitrarily different from the "true reward", which one would expect to get if the bandit was not corrupted. In such a case, we refer to these arbitrarily different rewards as outliers. The goal of the player is to maximize the expected reward obtained oblivious to the corruption. A Motivating Example. Though this article focuses on the theoretical aspects of this problem, we hereby illustrate a case study with roots in agriculture that motivates us. The Varroa mite is a pest that invades apiaries and causes destruction of bee colonies. There are numerous treatments that the beekeeper can use against the Varroa, such as applying amitraz or tau-fluvalinate [START_REF] Kamler | Comparison of taufluvalinate, acrinathrin, and amitraz effects on susceptible and resistant populations of varroa destructor in a vial test[END_REF] based pesticides, performing organic treatments like thymus or oxalic acid or thymus [START_REF] Gregorc | Use of thymol formulations, amitraz, and oxalic acid for the control of the varroa mite in honey bee (apis mellifera carnica) colonies[END_REF]. Every year, the beekeeper must rotate between treatments as the varroa develops resistance to a given treatment [START_REF] Frank D Rinkevich | Detection of amitraz resistance and reduced treatment efficacy in the varroa mite, varroa destructor, within commercial beekeeping operations[END_REF][START_REF] Kamler | Comparison of taufluvalinate, acrinathrin, and amitraz effects on susceptible and resistant populations of varroa destructor in a vial test[END_REF]. The reward of a treatment is dictated by the number of fallen varroa mites due to it. This reward function seems to be heavy-tailed and corrupted due to plethora of confounding variables, e.g. the weather, the way to administer the treatment, the state of the hive etc. [START_REF] Semkiw | The amitraz strips efficacy in control of varroa destructor after many years application of amitraz in apiaries[END_REF], which are hard to model. Interestingly, observed corruptions are natural and non-adversarial but probably unbounded. The heavy-tailed and corrupted nature of the problem resists application of the non-robust bandit algorithms, such as UCB, and motivates us to propose our setting: Bandits corrupted by Nature. Our Contributions. We consider the stochastic bandit with k arms of corrupted rewards {(1ε)P i + εH i } k i=1 . Here, P i 's are uncorrupted reward distributions with heavy-tails and bounded variances, H i 's are corruption distributions with probably unbounded corruptions, and ε ∈ [0, 1/2) is the proportion of corruption. This is equivalent to considering a setting where at every step Nature flips a coin with success probability ε. The player obtains a corrupted reward if Nature obtains 1 and otherwise, an uncorrupted reward. We call this setting 'Bandits corrupted by Nature'. Our setting encompasses both the heavy-tailed reward and unbounded corruptions. We formally define the setting and corresponding regret definition in Section 2.

In order to understand the fundamental hardness of the proposed setting, we derive the lower bounds on regret that illustrates the optimal regret achievable by any algorithm (Section 3). Lower bounds in Theorem 1 confirm that the heavy-tailed and corrupted bandits are harder than light-tailed bandits and there is an unavoidable cost to pay. It also indicates that though the logarithmic regret is asymptotically achievable, the hardness is dictated by the suboptimality gap ∆ i , 1 the variance of reward distributions σ i and the corruption proportion ϵ. Specifically, when δ i σ i 's are large, i.e. the optimal and the suboptimal arms are easy to distinguish, the effect due to this factor is inverse logarithmic and the effect due to corruption is proportional to (log( 1-ϵ ϵ )) -1 . On the other hand, if ∆ i σ i 's are small, i.e. we are in low distinguishability/high variance regime, the hardness is dictated by

σ 2 i ∆ 2 i,ε
. Here, ∆ i,ε ≜ ∆ i (1 -ε) -εσ i is the 'corrupted suboptimality gap' that replaces the traditional suboptimality gap ∆ i in the lower bound of non-corrupted and light-tailed bandits [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. Since ∆ i,ε ≤ ∆ i , it shows that in heavy-tailed and corrupt settings, it is harder to distinguish the optimal and suboptimal arms. They are the same when the corruption proportion ε = 0. Following the lower bounds, in Section 4, we design a robust algorithm, HuberUCB, that leverages the Huber's estimator for robust mean estimation. We derive a novel concentration inequality on the deviation of empirical Huber's estimate that allows us to design robust and tight confidence intervals for HuberUCB. In Theorem 3, we show that HuberUCB achieves the logarithmic regret, and also the optimal rate when the sub-optimality gap ∆ is not too large. In addition, we demonstrate that the regret of HuberUCB decomposes according to the respective values of ∆ i and σ i :

R n ≍   i:∆ i >σ i log(n)σ i   Error due to Heavy-tail + O   i:∆ i ≤σ i log(n)∆ i σ 2
Thus, our upper bound allows us to segregate the errors due to heavy-tail, corruption, and corruptioncorrection with heavy tails. Due to the corruption, we incur at least an error log(n

) ∆ i log( 1-ε ε )
, and instead of the usual log(n) σ i ∆ i , we obtain an error term log(n

)∆ i σ 2 i ∆ 2 i,ε
with the corrupted suboptimality gap. These observations resonate that of the lower bound, i.e. corrupted bandits are harder than uncorrupted ones as the corruption turns distinguishing the optimal arm from the suboptimal ones strictly harder. Due to the heavy-tail behaviour, we have the first term σ i log(n) that dominates the upper bound for ∆ i > σ i . Thus, the effect of heavy-tailedness separates from that of the corruption for large suboptimality gaps, where the optimal arm is easier to distinguish. In contrast, the effect of heavy-tailedness and corruption entangles and turns the optimal arm harder to detect, if the uncorrupted suboptimality gap is low. Thus, in the spirit of the lower bound, the upper bound of HuberUCB also shows the transition in hardness regime depending on ∆ i /σ i . In Section 5, we experimentally illustrate the claimed performance of HuberUCB for corrupted Gaussian and Pareto environments. For brevity, we defer the detailed proofs and the parameter tuning to Appendix.

Related Work. Due to the generality of our setting, this work extends the existing methods for both the heavy-tailed and corrupted bandits. While for designing the algorithm, it leverages on the literature of robust mean estimation. Here, we connect to these three streams of literature.

Heavy-tailed bandits. [START_REF] Bubeck | Bandits with heavy tail[END_REF] introduced the heavy-tailed bandits problem and uses robust mean estimator to propose RobustUCB algorithms. It sprouted research works leading to either tighter rates of convergence [START_REF] Lee | Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards[END_REF][START_REF] Agrawal | Regret minimization in heavy-tailed bandits[END_REF] or algorithms for structured environments [START_REF] Munoz | No-regret algorithms for heavy-tailed linear bandits[END_REF][START_REF] Shao | Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs[END_REF]. These works rely on the assumption that a bound on the (1+ϵ)-moment, i.e. E[|X| 1+ε ], is known for some ε > 0. We do not assume such a restrictive bound as knowing a bound on E[|X| 1+ε ] imply the knowledge of a bound on the sub-optimality gap ∆. Instead, we assume that the centered moment, specifically the variance, is bounded by a known constant. Thus, we address the open problem mentioned in [START_REF] Agrawal | Regret minimization in heavy-tailed bandits[END_REF] by relaxing the classical bounded (1+ϵ)-moment assumption with bounded centered moment.

Corrupted bandits. To our knowledge, the Bandits Corrupted by Nature is a novel setting for Bandits. Motivated by the agricultural and biological applications, we consider a non-adversarial proportion (ε ∈ [0, 1/2)) of corrupted samples with probably unbounded amount of corruptions. This is significantly different than the existing corrupted settings for bandits, which assume that the corruption is bounded and often the bound is known [START_REF] Lykouris | Stochastic bandits robust to adversarial corruptions[END_REF][START_REF] Bogunovic | Corruption-tolerant gaussian process bandit optimization[END_REF].

Robust mean estimation. Our algorithm design leverages the rich literature of robust means estimation, specifically the influence function representation of Huber's estimator. The problem of robust mean estimation in a corrupted and heavy-tailed setting stems from the work of Huber [START_REF] Peter | Robust estimation of a location parameter[END_REF](Huber, , 2004)). Recently, in tandem with machine learning, there has been numerous advances bth in the heavy-tailed [START_REF] Devroye | Sub-gaussian mean estimators[END_REF][START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF][START_REF] Minsker | Distributed statistical estimation and rates of convergence in normal approximation[END_REF] and in the corrupted settings [START_REF] Lecué | Robust machine learning by median-of-means: theory and practice[END_REF][START_REF] Minsker | Robust and efficient mean estimation: an approach based on the properties of self-normalized sums[END_REF][START_REF] Prasad | A unified approach to robust mean estimation[END_REF][START_REF] Prasad | A robust univariate mean estimator is all you need[END_REF][START_REF] Depersin | Robust subgaussian estimation of a mean vector in nearly linear time[END_REF][START_REF] Lerasle | Monk outlier-robust mean embedding estimation by median-of-means[END_REF][START_REF] Lecué | Robust machine learning by median-of-means: theory and practice[END_REF]. Our work, specifically the novel concentration inequality for Huber's estimator, adds a new result in this spirit.

Notations. We denote by P the set of probabilîty distributions on the real line R and P [q] ≜ {P ∈ P : E P [|X| q ] < ∞} the set of distributions with at least q ≥ 1 finite moments. 1{A} is the indicator function for the event A being true. We denote the mean of a distribution P i as

µ i ≜ E P i [X].

Bandits corrupted by Nature: Problem setting

In this section, we present the corrupted bandits setting that we study, and introduce the notion of regret decomposition for this setting. Importantly, the regret decomposition allows us to focus on the expected number of pulls of a suboptimal arm as the central quantity to control algorithmically.

Bandits corrupted by Nature

In the setting of Bandits corrupted by Nature, a bandit algorithm, or policy π, has access to k ∈ N uncorrupted reward distributions P 1 , . We call ν ε the law of the corrupted environment and we refer to the uncorrupted environment as ν. In this model of corruption, if C t = 1, the reward will be corrupted and obtaining C t = 1 does not depend on the value of X ′ t but rather on the global parameter ε. Thus, this model assumes independence of corruption, i.e. a non-adversarial behaviour of the Nature. Typically, one can think of agricultural applications in which such a setting would make sense because there does not seem to be an adversary that corrupts the data. The corruption is often due to external natural confounders, such as animals or weather, which are non-adversarial.

Remark 1 Let us highlight that we do not assume sub-Gaussian behaviour for the inlier distributions P i . Instead, we consider only a weak moment assumption: the inlier distributions P i have a finite variance. Thus, our setting is capable of modelling both heavy-tailed and corrupted settings. This enables our setting with a generality to develop algorithms for both of the problems. We testify this generality in the regret lower bounds and empirical performance analysis in Sections 3 and 5.

The Bandits corrupted by Nature model is equivalent to the classical finite-armed stochastic bandit setting with distributions {(1 -ε)P i + εH i } k i=1 . The main difference is how we assess the performance of an algorithm in this model: we try to quantify the effect of corruptions on the number of pulls or arms while ignoring the rewards coming from the H i 's. In the following section, we introduce a regret definition to explicate this connection.

Regret of corrupted bandits

We define the regret using the uncorrupted rewards instead of corrupted ones as otherwise it could always lead to arbitrarily bad regret. In this setting, the regret is the difference between the expected sum of uncorrupted rewards collected from the optimal arm and the expected sum of rewards collected by a bandit algorithm π operating under corrupted setting. Formally,

R n ≜ n max i E P i [X ′ ] -E n t=1 X ′ t . (1)
The randomness in the second expectation is taken with respect to a bandit algorithm π that reacts to the corrupted environment and the reward are those of the uncorrupted environment (X ′ ) n 1 . The first step is to decompose the regret over the arms as in Lemma 1.

Lemma 1 (Decomposition of corrupted regret) In a corrupted environment ν ε , the regret defined in Equation (1) can be decomposed as

R n = k i=1 ∆ i E ν ε [T i (n)] ,
where T i (n) ≜ n t=1 1{A t = i}, i.e. the number of pulls of arm i until time n, E ν ε [T i (n)] is the expected number of pulls of arm i until time n in the corrupted environment, and ∆ i ≜ max j µ j -µ i , which is called the suboptimality gap of arm i.

Lemma 1 states that the regret is the sum of the gaps in the uncorrupted environment times the expected number of pulls in the corrupted environment. Hence, we will focus on controlling

E ν ε [T i (n)],
i.e. the expected number of pulls of sub-optimal arms in the corrupted environment.

Lower bounds for uniformly good policies

In order to derive the lower bounds, we consider uniformly good policies on some family of environments with the set of laws

D = D 1 ⊗ • • • ⊗ D k , where D i ⊂ P for each i ∈ {1, . . . , k}. Definition 2 (Robust uniformly good policies) Let D ε = D ε 1 ⊗ • • • ⊗ D ε
k be a family of corrupted bandit environments on R. For a corrupted environment ν ε ∈ D ε with corresponding uncorrupted environment ν, let µ i (ν) be the mean reward of arm i in the uncorrupted setting and µ * (ν) ≜ max a µ i (ν) be the maximum mean reward. A policy π is uniformly good on D ε if for any α ∈ (0, 1],

∀ν ∈ D ε , ∀i ∈ {1, . . . , k}, µ i (ν) < µ * (ν) ⇒ E ν ε [T i (n)] = o(n α ).
In order to derive the lower bound, we rely on Lemma 2, which is a version of the change of measure argument [START_REF] Burnetas | Optimal adaptive policies for markov decision processes[END_REF], and can be found in (Maillard, 2019, Lemma 3.4).

Lemma 2 (Lower bound for uniformly good policies)

Let D = D 1 ⊗ • • • ⊗ D k ,
where D i ⊂ P for each i ∈ {1, . . . , k} and let ν ∈ D. Then, any uniformly good policy on D must pull arms such that for any

P i ∈ D i , i ∈ {1, . . . , k}, ∀i ∈ {1, . . . , k}, µ i ≤ µ * (ν) ⇒ lim inf n→∞ E ν [T i (n)] log(n) ≥ 1 KL(P i , P * )
.

Lemma 2 shows that it is sufficient to have an upper bound on the KL-divergence of the reward distributions interacting with the policy to get a lower bound on the number of pulls of a suboptimal arm. In the rest of this section, we compute upper bounds on the KL-divergences in some specific cases of heavy-tailed, such as Student's, and corrupted, such as Bernoulli, distributions. We leverage them for deriving the lower bounds on the number of pulls and hence, on the robust regret of a uniformly good policy.

Heavy-tails: Student's Distribution. To obtain a lower bound in the heavy-tailed case we use Student distributions. Student distribution are well adapted because they exhibit a finite number of finite moment which makes them heavy-tailed and we can easily change the mean and variances of Student distribution without changing its shape parameter ν.

Lemma 3 (Control of KL-divergence for Heavy-tails) Let P 1 , P 2 be two Student distributions with ν > 1 degrees of freedom with Corruption: Corrupted Bernoullis. We choose the corrupted Bernoulli distributions to get a lowerbound on the number of sub-optimal pulls in corrupted the setting. Let P 0 , P 1 be two Bernoulli distributions on {0, c} such that P P 0 (c) = P P 1 (0) > P P 0 (0) = P P 1 (c). We corrupt both P 0 and P 1 with a proportion ε > 0 to get

E P 1 [X] = 0 and E P 2 [X] = ∆. Then, KL(P 1 , P 2 ) ≤    3 ν-1 (ν+1) 2 ∆ 2 ν if ∆ ≤ 1 , (ν + 1) log (∆) + log 3 ν (ν+1) 2 ν if ∆ > 1 .
Q 0 ≜ (1 -ε)P 0 + εδ c and Q 1 ≜ (1 -ε)P 1 + εδ 0 .
We obtain Lemma 4 that illustrates three bounds on KL(Q 0 , Q 1 ) as functions of the suboptimality gap

∆ ≜ E P 0 [X] -E P 1 [X], variance σ 2 ≜ Var P 0 (X) = Var P 1 (X)
, and corruption proportion ϵ.

Lemma 4 (Control of KL-divergence for Corruptions) Let P 0 , P 1 be two Bernoulli probability distribution with ∆ = E P 0 [X] -E P 1 [X] and σ 2 = Var P 0 (X) = Var P 1 (X). There exists Q 0 and Q 1 , which are some ε-corruptions of P 0 and P 1 respectively with the shifted suboptiallity gap

∆ ε = ∆(1-ε)-εσ.
Given this, we have the following bounds on KL(Q 0 , Q 1 ).

• Uniform Bound. For any ∆, σ, we have

KL(Q 0 , Q 1 ) ≤ (1 -2ε) log 1 + 1 -2ε ε .
(2)

• High Distinguishability/Low Variance Regime. If σ ε √ 1-2ε < ∆ < σ, then KL(Q 0 , Q 1 ) ≤ ∆ ε σ log 1 + 2 ∆ ε σ -∆ ε .
(3)

• Low Distinguishability/High Variance Regime. If ∆ ≤ σ ε √ 1-2ε , then, there exists ε ′ ≤ ε and Q ′ 0 , Q ′ 1 some ε ′ -versions of P 0 and P 1 such that KL(Q ′ 0 , Q ′ 1 ) = 0.
Consequences of Lemma 4. We illustrate the bounds in Figure 1. The three upper bounds on the KL-divergence of corrupted Bernoullis provide us some insights regarding the impact of corruption. 1. Three Regimes of Corruption: We observe that depending on ∆/σ, we can categorise the corrupted environment in three categories. For ∆/σ ∈ [1, +∞), we observe that the KL-divergence between corrupted distributions Q 0 and Q 1 is upper bounded by a function of only corruption proportion ε and is independent of the uncorrupted distributions. Whereas for ∆/σ ∈ (ε/ √ 1 -2ε, 1), the distinguishability of corrupted distributions depend on the distinguishibility of uncorrupted distributions and also the corruption level. We call this the High Distinguishability/Low Variance Regime.

For ∆/σ ∈ [0, ε/ √ 1 -2ε],
we observe that the KL-divergence can always go to zero. We refer to this setting as the Low Distinguishability/High Variance Regime. 2. High Distinguishability/Low Variance Regime: In Lemma 4, we observe that the effective gap to distinguish the optimal arm to the closest suboptimal arm that dictates hardness of a bandit instance has shifted from the uncorrupted gap ∆ to a corrupted suboptimality gap:

∆ ε ≜ ∆(1 -ε) -εσ.
3. Low Distinguishability/High Variance Regime: We notice also that there is a limit for ∆ below which the corruption can make the two distributions Q 0 and Q 1 indistinguishable, this is a general phenomenon in the setting of testing in corruption neighbourhoods (see [START_REF] Peter | A robust version of the probability ratio test[END_REF]). Thus, in Figure 1, we observe that KL(Q 0 , Q 1 ) and the corresponding upper bound meet at zero. 4. Boundedness of KL under Corruption: Contrary to the usual setup, the KL between two corrupted Bernoullis is bounded as the corruption causes Q 0 and Q 1 to have the same support. 5. Limitations of the Bounds: Though the bounds are individually tight in their corresponding regimes, Figure 1 indicates looseness of them around σ. In future, it will be interesting to explore how these bounds can be pushed closer to the actual KL(Q 0 , Q 1 ) for ∆ σ close to 1. From KL Upper bounds to Regret Lower Bounds. We can substitute the results of Lemma 3 and 4 in Lemma 2 to get the lower bounds on regret of any uniformly good policy in a corrupted and heavy-tailed setting, where reward distributions belong to

P ε [2] = {(1 -ε)P + εH : H ∈ P and E P [|X| 2 ] < ∞}.
Theorem 1 (Lower bound for heavy-tailed and corrupted bandit)

Let D ε [2] ≜ P ε 2 ⊗ • • • ⊗ P ε 2 , and let ν ∈ D ε [2]
. Let i be a sub-optimal arm such that

E P i [X] ≤ max a E Pa [X] and denote ∆ i ≜ E P i [X] -max a E Pa [X] and ∆ i,ε ≜ ∆ i (1 -ε) -εσ i . • If ∆ i ≤ σ i /2, any uniformly good policy on D ε [2] satisfies lim inf n→∞ E ν ε [T i (n)] log(n) ≥ σ 2 i 2∆ 2 i,ε ∨ 1 log 1-ε ε . • If ∆ i ≥ σ i , any uniformly good policy on D ε [2] satisfies lim inf n→∞ E ν ε [T i (n)] log(n) ≥ 1 4 log 6∆ i σ i ∨ 1 log 1-ε ε .
Due to brevity, the detailed proof is deferred to Appendix B. In Theorem 1, if ∆ i is smaller than σ i , the term σ 2 i /∆ 2 i,ε represents the additional error due to corruption as well as the error due to heavy-tailedness. In the case where ∆ i is larger than σ i , we have a first term 1/4 log 6∆ i σ i that is due to heavy-tailedness. In both the cases, we obtain an unavoidable second term, 1/ log 1-ε ε , due to corruption. We also observe that when ∆ ε is small, we recover a lower bound with the factor σ 2 /2∆ 2 ε , which is analogous to inverse of the KL between Gaussians with variance σ 2 and a corrupted gap between means ∆ ε = ∆(1 -ε) -εσ. For ϵ = 0, this exactly leads to the lower bound for Gaussians with uncorrupted gap of means ∆ i and variance σ 2 i . In contrast, for ∆ i > σ i , it is not clear whether the term 1/ log(∆ i /σ i ) is tight because our upper bound do not exhibit this term but a constant error that does not go to zero as ∆ i /σ i go to infinity.

Robust bandit algorithm: Huber's estimator and upper bound on the regret

In this section we introduce an UCB-type algorithm adapted to our corrupted and heavy-tailed setup, see Algorithm 2. We further provide its theoretical guarantees in Theorem 3, showing that the rates of Theorem 1 are attained in some settings. Before that, we introduce and discuss Huber'sestimator.

Robust mean estimation and Huber's estimator

Now, we aim to design a UCB-type algorithm. In UCB, the focus is on mean estimation. Since the rewards are heavy-tailed and corrupted in our setting, we have to use a robust estimator of mean. We choose to use Huber's estimator [START_REF] Peter | Robust estimation of a location parameter[END_REF], an M-estimator that is known for its robust properties and have been extensively studied, specially the concentration properties [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF]).

Huber's estimator is a M-estimator, which means that it can be derived as a minimizer of some loss function. Let X 1 , . . . , X n be i.i.d. random variables and β > 0, we define Huber's estimator as Hub(X n 1 ) ∈ arg min θ∈R n i=1 ρ(X i -θ), where ρ is Huber's loss function with parameter β and X n 1 is shorthand notation for (X 1 , . . . , X n ). ρ is a loss function that is quadratic near 0 and linear near infinity, with β giving the limit between quadratic and linear behavior. In what follows, instead of this definition we will prefer the alternative one as a root of the following equation:

n i=1 ψ (X i -Hub(X n 1 )) = 0,
where the influence function ψ(x) ≜ x1{|x| ≤ β} + β sign(x)1{|x| > β}. We prefer this representation as we will show afterwards that the properties of Huber's estimator depend on ψ. β plays the role of a scaling parameter and depending on β, Huber's estimator is a trade-off between the efficiency of the minimizer of the square loss (i.e. the empirical mean) and the robustness of the minimizer of the absolute loss (i.e. the empirical median).

Concentration of Huber's estimator in corrupted setting

Let Hub(P ) be the theoretical counterpart of Hub(X n 1 ), defined for Y a random variable with law P by E[ψ(Y -Hub(P ))] = 0.

Theorem 2 (Concentration of Huber's estimator) We now state our first key result on the concentration of Huber's estimator in a corrupted and Heavy-tailed setting.

Suppose that X 1 , . . . , X n are i.i.d with law (1 -ε)P + εH for some P, H ∈ P and proportion of outliers ε ∈ (0, 1/2), and P having a finite variance σ 2 . Let p = P P (|Y

-E P [Y ]| ≤ β/2) with p > 5ε, β > 4σ. Let ε = (1-2ε) log( 1-ε ε ) and suppose δ ≥ exp -n 128(p-5ε) 2 49(1+2ε √ 2) 2
. Then, with probability larger than 1 -5δ,

|Hub(X n 1 ) -Hub(P )| ≤ σ 2 ln(1/δ) n + β ln(1/δ) 3n + 2βε ln(1/δ) n + 2βε p -ln(1/δ) 2n -ε + .
The Theorem 2 gives us the concentration of Hub(X n 1 ) around Hub(P ), the Huber functional of the inlier distribution P , there are a few details that must be explain to understand this Theorem: 1. Value of p: For most laws that exhibit some concentration properties, the constant p is close to 1 as β ≥ 4σ. One might also use Markov inequality to lower bound p. 2. Tightness of constants: If there are no outliers (ε = 0), the optimal rate of convergence in such a setting is at least of order σ 2 ln(1/δ)/n due to the central limit theorem. Theorem 2 shows that we are very close to attaining this optimal constant in the leading 1/ √ n term, this result for Huber's estimator was already present in [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF]. 3. Value of β: β is a parameter that achieve a trade-off between accuracy in the light-tailed uncorrupted setting and robustness. See the discussion in Section 4.4. 4. Restriction on value of δ: In Theorem 2, δ must be at least of order e -n , this restriction may seem arbitrary but it is in fact unavoidable as shown in (Devroye et al., 2016, Theorem 4.3). This is a limitation of robust mean estimation that will imply later a forced exploration that we will have to do at the beginning of our algorithm.

When P is non-symmetric, we need to control the distance to the mean |Hub(P ) -E[X]| (if P is symmetric, we have Hub(P ) = E[X]) to get a concentration of Hub(X n 1 ) around E[X]. We have the following lemma, direct consequence of (Mathieu, 2021, Lemma 4).

Lemma 5 (Bias of Huber's estimator) Let Y be a random variable with E[|Y | q ] < ∞ for q ≥ 2 and suppose that β 2 ≥ 9Var(Y ). Then

|E[Y ] -Hub(P )| ≤ 2E[|Y -E[Y ]| q ] (q -1)β q-1 .
Using Lemma 5 and Theorem 2, we can control the deviations of Hub(X n 1 ) from E[X]. This allows us to formulate an index-based algorithm (UCB-type algorithm) for corrupted Bandits. We present this algorithm in Section 4.3.

HuberUCB: Algorithm and regret bound

In this section, we describe a robust, UCB-type algorithm called HuberUCB. We denote µ i as the mean of arm i and σ 2 i its variance. We assume that we know the variances of the reward distributions. We refer to Section 4.4 for a discussion on the choice of the parameters when the reward distributions are unknown.

HuberUCB: The algorithm. In order to use the Huber's estimator in the multi-armed bandits setting, we need to estimate the mean of the rewards of each arms separately. We do that by defining a parameter β i for each arm and estimating separately each µ i using

Hub i,s = Hub (X t , 1 ≤ t ≤ s such that A t = i, ) . Denote for s ≥ s lim (t) = log(t) 98 128(p-5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2
, where ε =

(1-2ε) log( 1-ε ε ) , B i (s, t) = σ i 2 log(t 2 ) s + β i log(t 2 ) 3s + 2β i ε log(t 2 ) s + 2β i ε p -log(t 2 ) 2s -ε + b i ,
and

B i (s, t) = ∞ if s < s lim (t)
, where b i is a bound on the bias |E[X] -Hub(P i )|. This is zero if P i is symmetric and controlled by Lemma 5 otherwise. For example, one can take b i = 2σ 2 i /β 2 i .

Algorithm 2 HuberUCB for t = 1, . . . , n do Compute I i (t) for i ∈ {1, . . . , k} using X 1 , . . . , X t-1 .

Choose arm a t ∈ arg max i I i (t).

Observe a reward X t . end Then, we introduce HuberUCB (Algorithm 2), which selects an arm a t based on the index I i (t) = Hub i,T i (t-1) + B i (T i (t -1), t). We now provide the main regret guarantee of this strategy.

Theorem 3 (Upper Bound on Regret of HuberUCB) Suppose that for all i,P i is a distribution with finite variance σ 2 i . Suppose 4σ i ≤ β i and p = inf 1≤i≤k P P i (|X -

E P i [X]| ≤ β i /2) with p > 5ε (in particular ε < 1/5). Also, ∆ i,ε = (∆ i -2b i )(p -ε) -8β i ε > 0 and (1-2ε) log( 1-ε ε ) ≤ ε. • If ∆ i,ε > 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 , then E[T i (n)] ≤ log(n) max 32β i 3 ∆ i,ε , 4 (p-5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 + 10(log(n)+1) • If ∆ i,ε ≤ 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 , then E[T i (n)] ≤ log(n) max 50σ 2 i 9 ∆ 2 i,ε √ 2+2 β i σ i ε 2 , 4 (p-5ε) 2 1+2 √ 2 ε ∨ 9 14 √ 2 2 +10(log(n)+1).
We now state a simplified version of Theorem 3 with bad but explicit constants for easier understanding. Let β 2 i = 16σ 2 i , ε ≤ 1/10 so that ε = 4/(5 ln( 9)) ≃ 0.54, p ≥ 1-

4σ 2 i β 2 i ≥ 3 4 ≥ 5ε+ 1
4 and suppose P i symmetric so that b i = 0. Further simplifying the constants yields the following.

Corollary 1 (Simplified version of Theorem 3) Suppose that for all i,P i is a distribution with finite variance

σ 2 i . Denote ∆ i,ε = ∆ i (p -ε) -32σ i ε, • If ∆ i,ε > 6σ i 1 + 4 √ 2ε 2 , then E[T i (n)] ≤ 43 log(n) max σ i ∆ i,ε , 12ε 2 + 6 + 10(log(n) + 1). • If ∆ i,ε ≤ 6σ i 1 + 4 √ 2ε 2 , then E[T i (n)] ≤ 23 log(n) max σ 2 i ∆ 2 i,ε
1 + 32ε 2 , 24ε 2 + 12 + 10(log(n) + 1).

We see that up to the constants, in the case ∆ i,ε small, we recover the rate of convergences of Theorem 1. Indeed, in Theorem 1 and Corollary 1, when ∆ i is small compared to σ i , we recover the

error term E[T i (n)] ≍ log(n) σ 2 i ∆ 2 i,ε ∨ ε 2 . On the other hand, if ∆ i is large compared to σ i , we get that E[T i (n)] ≤ O log(n) σ i ∆ i,ε ∨ ε 2 ∨ 1 ≤ O log(n) 1 ∨ ε 2
, the rate of convergence of our algorithm is sub-optimal but this was unavoidable due to the forced exploration we have to give to our algorithm (the s lim (t)). This forced exploration seems necessary in our approach in order to be able to handle the case ∆ i ≤ σ i .

Discussion

We discuss some properties of HuberUCB and compare it with RobustUCB [START_REF] Bubeck | Bandits with heavy tail[END_REF].

Choice of β, σ and ε. HuberUCB depends on three hyperparameters that we have to choose. In Theorem 3, we assume to know the σ and ε. In practice, these are unknown and we estimate σ 2 with a robust estimator of the variance, such as the median absolute deviation. Ideally, β should be larger than σ by some constant factor. We recommend to use the estimator of σ to estimate a good value of β. In contrast, estimating ε is hard. However one can use the conservative upper bound ε = 0.5. We refer to Appendix H for an empirical study of the choice of β and ε.

Comparison with Heavy-tail bandits. Linked to the problem of chosing β is the difference between heavy-tailed bandits and corrupted bandits. When the data are heavy-tailed but not corrupted, [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF] shows that β ≃ σ √ n is a good choice for the scaling parameter. However, this choice is not robust to outliers and yields a linear regret in our setup (see Section 5). When there is corruption, β must remains bounded when the sample size goes to infinity in order to stay robust. Computational cost. Huber's estimator has linear complexity due to the involved Iterated Reweighting Least Squares algorithm, which is not sequential. We have to do this at every iteration, which leads HuberUCB to have quadratic time complexity. This seems to be the price for robustness.

Experimental Analysis

In this section, we assess the experimental efficiency of HuberUCB by plotting the empirical regret. Contrary to the uncorrupted case, we cannot really estimate the regret in Equation (1) using the observed regret. Instead, we use the theoretical uncorrupted gaps that we know because we are in a simulated environment and we estimate the regret R n using Regret = k i=1 ∆ i T i (n), where

T i (n) = 1 M M m=1 (T i (n)) m is a Monte-Carlo estimation of E ν ε [T i (n)]
over M experiments. We used rlberry python library Domingues et al. ( 2021) for the experiments. Comparison to bandit algorithms for Heavy-tailed setting. There is, to our knowledge, no existing bandit algorithm for the corruption setting prior to this work, hence we focus on comparing ourselves to the closest relatives: bandits in heavy-tailed setting. We empirically and competitively study three different algorithms: HuberUCB and two RobustUCB algorithms with Catoni Huber estimator and Median of Means (MOM) [START_REF] Bubeck | Bandits with heavy tail[END_REF]. HuberUCB is closely related to the RobustUCB with Catoni Huber estimator, which also uses Huber's estimator but with another set of parameters and confidence intervals. The RobustUCB algorithms are tuned for uncorrupted heavy-tails. Hence, they incur linear regret in a truly corrupted setting and this is reflected in the experiments. We also improve upon [START_REF] Bubeck | Bandits with heavy tail[END_REF] as we can handle arm-dependent variances. Corrupted Gaussian setting: In Figure 2 (top), we study a 3-armed bandits with corrupted Gaussian distributions having means 0, 0.9, 1 and standard deviation 0.1. The corruption applied to this bandit problem are Gaussians with variance 1 and centered in 100, 100 and -1000 respectively. For HuberUCH, we chose to use β i = 4σ i . We perform each experiment 100 times to get a Monte-Carlo error estimation. We plot the mean plus/minus the standard deviation of the result in Figure 2. We do that for the three corruption proportions ε equal to 0%, 3% and 5%. We notice that there is a short linear regret phase at the beginning due to the forced exploration performed by the three algorithms. Followed by that, HuberUCB incurs seemingly logarithmic regret. On the other hand, for Catoni Huber Agent and MOM Agent, the regret is logarithmic only in the uncorrupted setting. When the data are corrupted, i.e. ε > 0, the regret becomes linear. Corrupted pareto setting: In Figure 2 (bottom), we illustrate the results for a 3-armed bandits with corrupted pareto distributions having shape parameters 3, 4 and 5 (i.e. 2, 3, and 4 finite moments) and scale parameters 0.1, 0.2, 0.3. Thus, the corresponding means are 0.15, 0.27 and 0.37 and the standard deviations are 0.3, 0.4, 0.5, respectively. The corruption applied to this bandit problem are Gaussians with variance 1 and centered in respectively 100, 100 and -1000 respectively. For HuberUCB, we chose to use β = 3σ i and we also bound the bias b i by σ 2 i /β i . The results echoes the observations for the Gaussian case except that the learning process takes more time.

Conclusion

In this paper, we study the setting of Bandits corrupted by Nature that encompasses both the heavytailed rewards with bounded variance and unbounded corruptions in rewards. In this setting, we prove lower bounds on the regret that shows the heavy-tail bandits and corrupted bandits are strictly harder than the usual sub-gaussian bandits. Specifically, in this setting, the hardness depends on the suboptimality gap/variance regimes. If the suboptimality gap is small, the hardness is dictated by

σ 2 i /∆ 2 i,ε .
Here, ∆ i,ε is the corrupted suboptimality gap, which is smaller than the uncorrupted gap ∆ and thus, harder to distinguish. To complement the lower bounds, we design a robust algorithm HuberUCB that uses Huber's estimator for robust mean estimation and a novel concentration bound on this estimator to create tight confidence intervals. HuberUCB achieves logarithmic regret that matches the lower bound for low suboptimality gap/high variance regime. Unlike existing literature, we do not need any assumption on a known bound on corruption and a known bound on the (1 + ϵ)uncentered moment, which was posed as an open problem in [START_REF] Agrawal | Regret minimization in heavy-tailed bandits[END_REF].

Since our upper and lower bounds disagree in the high gap/low variance regime, it will be interesting to investigate this regime further. Also, following the literature, it will be natural to extend HuberUCB to contextual and linear bandit settings with corruptions and heavy-tails. This will facilitate its applicability to practical problems, such as choosing treatments against pests.

Appendix A. Proof of Lemma 1: Regret Decomposition

From Equation (1), we have

R n = k a=1 n t=1 E (max a E Pa [X ′ ] -X ′ t )1 {A t = a} Then, we condition on A t E (max a E Pa [X ′ ] -X ′ t )1 {A t = a} |A t = 1{A t = a}E[max a E Pa [X ′ ] -X ′ t |A t ] = 1{A t = a}(max a E Pa [X ′ ] -µ At ) = 1{A t = a}(max a E Pa [X ′ ] -µ a ) = 1{A t = a}∆ a
and this stays true whatever the policy, because the policy at time t use knowledge up to time t -1, hence its decision does not depend on X t . Hence, we have

R n (π) = k a=1 ∆ a E π(•|X n 1 ,A n 1 ) [T a (n)]
where T a (n) is with respect to the randomness of π, which is to say that we compute E[T i (n)] in the corrupted setting and not in the uncorrupted one.

R n = k a=1 ∆ a E νε [T a (n)] .

Appendix B. Proof of Theorem 1: Regret Lower Bound

From Lemma 2, we have

lim inf n→∞ E ν [T i (n)] log(n) ≥ 1 KL(P 0 , P 1 ) ∨ 1 KL(Q 0 , Q 1 ) (4)
where P 0 , P 1 are student distributions with parameter ν = 3 and gap ∆ i as in Lemma 3 renormalized so that the variance is σ 2 i , and Q 0 , Q 1 are as in Lemma 4 with gap ∆ i and variance σ i . From Lemma 3, we get

KL(P 1 , P 2 ) ≤    3 ν-1 (ν+1) 2 ∆ 2 i σ 2 i (ν-2) if ∆ 2 i ≤ ν-2 ν σ 2 i ν+1 2 log ν σ 2 i (ν-2) ∆ 2 i + log 3 ν (ν+1) 2 ν if ∆ 2 i > ν-2 ν σ 2 i
Hence, with ν = 3,

KL(P 1 , P 2 ) ≤    144∆ 2 i σ 2 i if ∆ 2 i ≤ σ 2 i /3 2 log 3∆ 2 i σ 2 i + log (144) if ∆ 2 i > σ 2 i /3 (5)
First setting:

If ∆ i ≤ σ i /2, then ∆ 2 i ≤ σ 2
i /3 and from Equations ( 5) and ( 4) and Lemma 4,

lim inf n→∞ E ν [T i (n)] log(n) ≥ σ 2 i 144∆ 2 i ∨ σ i ∆ i,ε log 1 + ∆ i,ε σ i -∆ i,ε Then, use that ∆ i,ε ≤ ∆ i ≤ σ i /2, log 1 + ∆ i,ε σ i -∆ i,ε ≤ ∆ i,ε σ i -∆ i,ε ≤ 2∆ i,ε σ i
Hence, considering also the term from Equation (2) in Lemma 4,

lim inf n→∞ E ν [T i (n)] log(n) ≥ σ 2 i 144∆ 2 i ∨ σ 2 i 2∆ 2 i,ε ∨ 1 log 1-ε ε
We weaken this inequality to the simplified version found in Theorem 1 by dropping the second term on the right-hand side for better interpretability.

Second setting:

If ∆ i > σ i , then ∆ 2 i > σ 2
i /3 and from Equations ( 5) and ( 4) and Lemma 4, First, we compute the χ 2 divergence between the two laws f a and f 0 . We have, for any a ∈ R

lim inf n→∞ E ν [T i (n)] log(n) ≥ 1 2 log 3∆ 2 i σ 2 i + log (144) ∨ 1 log 1-ε ε = 1 4 log √ 3∆ i σ i + 4 log 2 √ 3 ∨ 1 log 1-ε ε = 1 4 log 6∆ i σ i ∨ 1 log 1-ε ε Appendix C. Upper
d χ 2 (f a , f 0 ) = (f a (x) -f 0 (x)) 2 f 0 (x) dx = Γ k+1 2 Γ k 2 √ kπ R     1 1 + (x-a) 2 k k+1 2 - 1 1 + x 2 k k+1 2     2 1 + x 2 k k+1 2 dx = Γ k+1 2 Γ k 2 √ kπ R 1 + (x-a) 2 k k+1 2 -1 + x 2 k k+1 2 2 1 + (x-a) 2 k k+1 1 + x 2 k k+1 2 dx = Γ k+1 2 Γ k 2 √ kπ     R dx 1 + x 2 k k+1 2 -2 R dx 1 + (x-a) 2 k k+1 2 + R 1 + x 2 k k+1 2 1 + (x-a) 2 k k+1 dx     .
The first two terms are respectively equal to 1 and -2 using the fact that the student distribution integrate to 1. Then, we do the change of variable y = x -a in the last integral to get

d χ 2 (f a , f 0 ) = Γ k+1 2 Γ k 2 √ kπ R 1 + (y+a) 2 k k+1 2 1 + y 2 k k+1 dy -1.
this is a polynomial of degree k in the variable a. We have the following Lemma proven in Section G.1.

Lemma 6 For a ∈ R and k ≥ 0, we have the following algebraic inequality.

R 1 + (y+a) 2 k k+1 2 1 + y 2 k k+1 dy ≤ 2 a 2 √ k (k + 1) 2 2 + a √ k k-1 + R (1 + y 2 /k) k+1 2 1 + y 2 k k+1 dy
Using this lemma, and because we recognize up to a constant the integral of the student distribution on R in the right hand side, we have [START_REF] Wendel | Note on the gamma function[END_REF], hence

d χ 2 (f a , f 0 ) = Γ k+1 2 Γ k 2 √ kπ   2 a 2 √ k (k + 1) 2 2 + a √ k k-1 + R (1 + y 2 /k) k+1 2 1 + y 2 k k+1 dy    -1 ≤ Γ k+1 2 Γ k 2 √ kπ 2 a 2 √ k (k + 1) 2 2 + a √ k k-1 then, use that for any k ≥ 1, Γ( k+1 2 ) ≤ Γ( k 2 ) k/2 from
d χ 2 (f a , f 0 ) ≤ a 2 (k + 1) 2 √ 2 k √ π 2 + a √ k k-1 ≤ a 2 (k + 1) 2 k 2 + a √ k k-1
Then, we use the link between KL divergence and χ 2 divergence to get the result.

KL(f a , f 0 ) ≤ log(1 + d χ 2 (f a , f 0 )) ≤ log 1 + a 2 (k + 1) 2 k 2 + a √ k k-1 (6)
Then, use that

log 1 + a 2 (k + 1) 2 k 2 + a √ k k-1 ≤    log 1 + 3 k-1 (k+1) 2 k a 2 if a < 1 log 1 + 3 k-1 (k+1) 2 k a k+1 if a ≥ 1 hence, using that 1 ≤ 3 k-1 (k+1) 2 k a k+1 log 1 + a 2 (k + 1) 2 k 2 + a √ k k-1 ≤    3 k-1 (k+1) 2 k a 2 if a < 1 (k + 1) log (a) + log 3 k (k+1) 2 k if a ≥ 1
Inject this in Equation ( 6) to get the result.

C.2. Proof of Lemma 4: Corrupted Bernoulli Distribution

Let α ∈ (0, 1/2) and c > 0. Define

P 0 = (1 -α)δ 0 + αδ c , P 1 = αδ 0 + (1 -α)δ c , Q 0 = (1 -ε)(1 -α)δ 0 + (1 -(1 -ε)(1 -α))δ c , Q 1 = (1 -(1 -ε)(1 -α))δ 0 + (1 -ε)(1 -α)δ c .
One can check that Q 0 = (1 -ε)P 0 εδ c and Q 1 = (1 -ε)P 1 + εδ 0 and hence Q 0 and Q 1 are in the ε-corrupted neighborhood of respectively P 0 and P 1 .

We have

KL(Q 0 , Q 1 ) = k∈{0,c} P Q 0 (X = k) log P Q 0 (X = k) P Q 1 (X = k) = (1 -ε)(1 -α) log (1 -ε)(1 -α) 1 -(1 -ε)(1 -α) + (1 -(1 -ε)(1 -α)) log 1 -(1 -ε)(1 -α) (1 -ε)(1 -α) = ((1 -ε)(1 -α) -(1 -(1 -ε)(1 -α))) log (1 -ε)(1 -α) 1 -(1 -ε)(1 -α) = (1 -2ε -2α + 2εα) log 1 + 1 -2ε -2α + 2εα ε + α -εα Then, note that ∆ = E P 1 [X] -E P 0 [X] = (1 -2α)c and σ 2 = Var P 0 (X) = Var P 1 (X) = α(1 -α)c 2 . Hence, c = √ ∆ 2 + σ 2 and α = 1 2 1 -∆/ √ ∆ 2 + σ 2 . KL(Q 0 , Q 1 ) = 1 -2ε -1 - ∆ √ ∆ 2 + σ 2 (1 -ε) log   1 + 1 -2ε -1 - ∆ √ ∆ 2 +σ 2 (1 -ε) ε + 1 2 1 - ∆ √ ∆ 2 +σ 2 (1 -ε)   = ∆ √ ∆ 2 + σ 2 (1 -ε) -ε log 1 + ∆ √ ∆ 2 +σ 2 (1 -ε) -ε 1 2 (1 + ε) -1 2 ∆ √ ∆ 2 +σ 2 (1 -ε)
In the setting σ > ∆, we have the bound

KL(Q 0 , Q 1 ) ≤ ∆ σ (1 -ε) -ε log 1 + 2 ∆ σ (1 -ε) -ε 1 -∆ σ (1 -ε) -ε
On the other hand, if ε > 0, we have

KL(Q 0 , Q 1 ) ≤ (1 -2ε) log 1 + 1 -2ε ε .
Appendix D. Regret Upper Bounds for HuberUCB: Proofs of Theorem 3 and Corollary 1

If A t = i then at least one of the following four inequalities is true:

Hub 1,T 1 (t-1) + B 1 (T 1 (t -1), t) ≤ µ 1 (7) or Hub i,T i (t-1) ≥ µ i + B i (T i (t -1), t) (8) or ∆ i < 2B i (T i (t -1), t) (9)
or

T 1 (t -1) < s lim (t) = 98 log(t) 128 (p -5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 (10)
Indeed, if T i (t -1) < s lim (t), then B i (T i (t -1), t) = ∞ and Inequality ( 9) is true. On the other hand, if T i (t -1) ≥ s lim (t), then we have B i (T i (t -1), t) is finite and all four inequalities are false, then,

Hub 1,T 1 (t-1) + B 1 (T 1 (t -1), t) > µ 1 = µ i + ∆ i ≥ µ i + 2B i (T i (t -1), n) ≥ µ i + 2B i (T i (t -1), t) ≥ Hub i,T i (t-1) + B i (T i (t -1), t)
which implies that A t ̸ = i.

Step 1. We have that P (7 is true) ≤ 5/t. PROOF:

Then, we have that,

P Hub 1,T 1 (t-1) + B 1 (T 1 (t -1), t) ≤ µ 1 ≤ t s=1 P Hub 1,s + B 1 (s, t) ≤ µ 1 = t s=⌈s lim (t)⌉ P Hub 1,s -µ 1 ≤ -B 1 (s, t)
Then, use Theorem 2, we get

P Hub 1,T 1 (t-1) + B 1 (T 1 (t -1), t) ≤ µ 1 ≤ t s=⌈s lim (t)⌉ 5e -log(t 2 ) ≤ t s=⌈s lim (t)⌉ 5 t 2 ≤ 5 t .
Step 2. Similarly, for arm i, we have

P Hub i,T i (t-1) ≥ µ i + B i (T i (t -1), t) ≤ 5 t PROOF: We have, P Hub i,T i (t-1) ≥ µ i + B i (T i (t -1), t) ≤ t s=⌈s lim (t)⌉ P Hub i,s -µ i ≥ B i (s, t) ≤ t s=⌈s lim (t)⌉ 5e -log(t 2 ) ≤ 5 t .
Step 3. Let v ∈ N. If one of the two following conditions are true, then for all t such that T i (t-1) ≥ v, we have ∆ i ≥ 2B i (T i (t -1), t) (i.e. Equation ( 9) is false).

Condition 1: if ∆ i,ε > 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 and v ≤ log(n) 96β i 9 ∆ i,ε . Condition 2: if ∆ i,ε ≤ 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 and v ≤ 50 9 ∆ 2 i,ε σ i √ 2 + 2β i ε 2 log(n). PROOF: We search for the smallest value v ≥ s lim (n) such that ∆ i verifies ∆ i ≥ 2B i (v, n) = 2 σ i 2 log(n 2 ) v + β log(n 2 ) 3v + 2εβ i log(n 2 ) v + 2β i ε p -log(n 2 ) 2v -ε + 2b i .
First, we simplify the expression, having that v ≥ s lim (n), we have

log(n 2 ) 2v ≤ 128(p -5ε) 2 98(1 + 9/7) 2 ≤ (p -ε) 2 4 ,
hence we simplify to

∆ i ≥ 4 (p -ε) σ i 2 log(n 2 ) v + β i log(n 2 ) 3v + 2β i ε log(n 2 ) v + 2β i ε + 2b i let us denote ∆ i,ε = (∆ i -2b i )(p -ε) -8β i ε, we are searching for v such that β i log(n 2 ) 3v + log(n 2 ) v σ i √ 2 + 2β i ε - ∆ i,ε 4 ≤ 0
This is a second order polynomial in log(n 2 )/v.

If ∆ i,ε > 0, then the smallest v > 0 is log(n 2 ) v = 3 2β i   -σ i √ 2 + 2εβ i + σ i √ 2 + 2β i ε 2 + ∆ i,ε β i 3   . First setting: if ∆ i,ε > 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 ,
In that case, we have

log(n 2 ) v ≥ 3 2β i   -σ i √ 2 + 2β i ε + β i ∆ i,ε 3   ≥ 3 2β i β i ∆ i,ε 12 = 9 ∆ i,ε 48β i Hence, v ≤ log(n) 96β i 9 ∆ i,ε . Second setting: if ∆ i,ε ≤ 12 σ 2 i β i √ 2 + 2 β i σ i ε 2
, then we use Lemma 9, using that

∆ i,ε β i 3 σ i √ 2 + 2β i ε 2 ≤ 4
and the fact that

√ 1+4-1 4 ≥ 3 10 , we get, log(n 2 ) v ≥ 3 ∆ i,ε 5 σ i √ 2 + 2β i ε Hence, v ≤ 50 9 ∆ 2 i,ε σ i √ 2 + 2β i ε 2 log(n).
Step 4. Using All the previous steps, we prove the theorem. PROOF: We have

E[T i (n)] = E n t=1 1{A t = i} ≤ ⌊max(v, s lim (n))⌋ + E   n t=⌊max(v,s lim (n))⌋+1 1{A t = i and (9) is false}   ≤ ⌊max(v, s lim (n))⌋ + E   n t=⌊max(v,s lim (n))⌋+1
1{( 7) or ( 8) or ( 10) is true}

  = ⌊max(v, s lim (n))⌋ + n t=⌊min(v,s lim (n))⌋+1 P ((7) or (8) is true) ≤ ⌊max(v, s lim (n))⌋ + 2 n t=⌊min(v,s lim (n))⌋+1
5 t using the harmonic series bound by log(n) + 1, we have

E[T i (n)] ≤ max(v, s lim (n)) + 10(log(n) + 1)
Then, we replace the value of v, First setting: ∆ i,ε > 12

σ 2 i β i √ 2 + 2 β i σ i ε 2 E[T i (n)] ≤ log(n) max 96β i 9 ∆ i,ε , 4 (p -5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 + 10(log(n) + 1) Second setting: if ∆ i,ε ≤ 12 σ 2 i β i √ 2 + 2 β i σ i ε 2 , then E[T i (n)] ≤ log(n) max 50 9 ∆ 2 i,ε σ i √ 2 + 2β i ε 2 , 4 (p -5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 +10(log(n)+1).
This concludes the proof of Theorem 3.

D.1. Proof of Corollary 1: Simplified Upper Bound of HuberUCB

Replacing β i by 4σ i , we have

• If ∆ i,ε > 6σ i 1 + 4 √ 2ε 2 , then E[T i (n)] ≤ log(n) max 128σ i 3 ∆ i,ε , 4 (p -5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 + 10(log(n) + 1) • If ∆ i,ε > 6σ i 1 + 4 √ 2ε 2 , then E[T i (n)] ≤ log(n) max 50σ 2 i 9 ∆ 2 i,ε √ 2 + 8ε 2 , 4 (p -5ε) 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 +10(log(n)+1).
Then, we use that where V ψ = Var(ψ(Y i -Hub(P ))).

1 + 2 √ 2 ε ∨ 9 14 √ 2 2 ≤ 2 1 + 2 √ 2 ε ∨ 9 14 √ 2 2 = 2 +
Then, using that Bernoulli random variables with mean ε are sub-Gaussian with variance parameter 1-2ε 2 log((1-ε)/ε) (see (Bourel et al., 2020, Lemma 6)),

P 1 n n i=1 1{W i = 1} ≤ ε + ln(1/δ)(1 -2ε) n log 1-ε ε ≥ 1 -δ.
Then, using Lemma 7 we get for any δ ∈ (0, 1), with probability larger than 1 -3δ,

1
This is a polynomial in ln(1/δ)/n that we need to solve. We use the following elementary algebra lemma.

Lemma 9 (2nd order polynomial root bound) let a, b, c be three positive constants and x verify ax 2 + bx -c ≤ 0. Suppose that 4ac b 2 ≤ d, then x verifies

x ≥ 2c( √ d + 1 -1) db .

Observe that we have 2 (p -5ε)

3 1 √ 2 + 2 √ 1-2ε log( 1-ε ε ) 2 ≤ 4 3
Step 1. For any λ > 0, P(∃n ≤ N : |∆ n | ≥ λ) ≤ P(∃n ≤ N : f n (λ) ≥ 0). PROOF: For all y ∈ R, let J n (y) = 1 n n i=1 ρ(X i -y) we have,

J ′′ n (y) = 1 n n i=1
ψ ′ (X i -y) .

In particular, having f n (λ) = -sign(∆ n )J ′ (Hub(P ) + λ sign(∆ n )) if we take the derivative of f n with respect to λ, we have the following equation

∂ ∂λ f n (λ) = -sign(∆ n ) 2 J ′′ n (Hub(P ) + λ sign(∆ n )) ≤ - 1 n n i=1
ψ ′ (X i -Hub(P ) -λ sign(∆ n )).

Then, because ψ ′ is non-negative, the function λ → f n (λ, ) is non-increasing. Hence, for all n ∈ N * and λ > 0,

|∆ n | ≥ λ ⇒ f n (|∆ n |) = 0 ≤ f n (λ),
Step 2. For all λ > 0,

f n (λ) ≤ f n (0) -λ inf t∈[0,λ]
f ′ n (t) .

PROOF: We apply Taylor's inequality to the function f n . As f n is non-increasing (because its derivative is non-positive, see Equation ( 13)), we get

f n (λ) ≤ f n (0) -λ inf t∈[0,λ] f ′ n (t) .
Step 3. Let m n = E inf t∈[0,λ]

1 n n i=1 ψ ′ (X ′ i -

G.2. Proof of Lemma 9

The solutions of the second order polynomial indicate that x must verify

x ≥ -b + √ b 2 + 4ac 2a ≥ b 2a -1 + 1 + 4ac b 2 .
Then, use that the function x → √ x + 1 is concave and hence the graph of x → √ x + 1 is above its chords and we have for any x ∈ [0, d],

√ 1 + x ≥ 1 + x √ d+1-1 d . Hence, x ≥ b 2a 4ac( √ d + 1 -1) db 2 = 2c( √ d + 1 -1) db .

Figure 1 :

 1 Figure 1: Plot of the KL and the bounds for σ=1 and ε = 0.2 (x axis is in log scale)

Figure 2 :

 2 Figure 2: Cumulative regret plot of the algorithms on a corrupted Gaussian (above) and Pareto (below) datasets with various corruption proportions.

  Bounds on KL-divergence: Student's and Corrupted Bernoulli C.1. Proof of Lemma 3: Student's Distribution

  ≤ N : |∆ n | ≥ λ) ≤ P(∃n ≤ N : f n (λ) ≥ 0).

  . . , P k ∈ P[q] and k corrupted reward distributions H 1 , . . . , H k ∈ P. At each step t ∈ {0, . . . , n}, Nature draws a random variable C t ∈ {0, 1} from a Bernoulli distribution with mean ε ∈ [0, 1/2). If C t = 1, the reward will be drawn from the corrupted distribution H At corresponding to the chosen arm A t ∈ {1, . . . , k}. Otherwise, it will come from the uncorrupted distribution P At . The policy π interacts with these corrupted environment by choosing an arm A t and obtaining a reward corrupted by Nature X t . The policy leverages these observations to choose another arm at the next step so that it maximises the total cumulative reward obtained after n steps. In Algorithm 1, we outline a pseudocode of this problem.

	Algorithm 1 Bandits corrupted by Nature
	Parameters: ε ∈ [0, 1/2) and q ≥ 2
	Data: P 1 , . . . , P k ∈ P [q] be the uncorrupted reward distributions and H 1 , . . . , H k ∈ P be the
	corrupted reward distributions.
	for t = 1, . . . , n do
	Player plays an arm A t ∈ {1, . . . , k}
	Nature draws a Bernoulli C t ∼ Ber(ε)
	Generate a corrupted reward Z t ∼ H At and an uncorrupted reward X ′ t ∼ P At Player observe the reward X t = X ′ t 1{C t = 0} + Z t 1{C t = 1}
	end

  Remark that by definition of Hub(P ), it is defined as the root of the equation E[ψ(Y -Hub(P ))] = 0. From Bernstein's inequality, for any δ ∈ (0, 1),

	P	1 n	n i=1	ψ(Y i -Hub(P )) ≥	2V ψ ln(1/δ) n	+ β	ln(1/δ) 3n	≤ 2δ
									8 ε 2 ∨	81 392	≤ 8ε 2 + 2 +	648 392	≤ 8ε 2 + 4
	and that p -5ε ≥ 1/4, to get • If ∆ i,ε > 6σ i 1 + 4 √ 2ε	2 , then
	E[T i (n)] ≤ log(n) max	128σ i 3 ∆ i,ε	, 512ε 2 + 256 + 10(log(n) + 1)
			=	128 3	log(n) max	σ i ∆ i,ε	, 12ε 2 + 6 + 10(log(n) + 1)
			≤ 43 log(n) max	σ i ∆ i,ε	, 12ε 2 + 6 + 10(log(n) + 1)

  n Using η = ln(1/δ) 2n , the hypotheses of Lemma 8 are verified. PROOF: To apply Lemma 8, it is sufficient that

	n i=1	ψ(X i -Hub(P )) ≤ σ	2 ln(1/δ) n	+ β	ln(1/δ) 2n	+ 2βε + 2β	ln(1/δ)(1 -2ε) n log 1-ε
		σ	2t n	+ β	ln(1/δ) 3n	+ 2β	ln(1/δ)(1 -2ε) n log 1-ε ε	≤	β 2	p -	ln(1/δ) 2n	-ε
	and using that 4σ ≤ β, we have that it is sufficient that
				ln(1/δ) 2n	+	ln(1/δ) 3n	+ 2	ln(1/δ)(1 -2ε) n log 1-ε ε	≤	1 2	(p -5ε) .

ε .

Step 2.

  Hub(P ) -t) . With probability larger than 1 -2e -2nη 2 ,

	inf t∈[0,λ]	f ′ n (t)) ≥ m n -2η -ε,

PROOF: Write that X i = (1-W i )Y i +W i Z i where W 1 , . . . ,

W n are i.i.d Bernoulli random variable with mean ε, Y 1 , . . . , Y n are i.i.d ∼ P and Z 1 , . . . , Z n are i.i.d with law H.

© 2022 D. Basu, O.-A. Maillard & T. Mathieu.

Acknowledgments

This work has been supported by the French Ministry of Higher Education and Research, the Hautsde-France region, Inria, the MEL, the I-Site ULNE regarding project R-PILOTE-19-004-APPRENF, and the Inria A.Ex. SR4SG project.

2 , 512ε 2 + 256 + 10(log(n) + 1)

2 + 64ε 2 , 512ε 2 + 256 + 10(log(n) + 1)

1 + 32ε 2 , 24ε 2 + 12 + 10(log(n) + 1)

Appendix E. Proof of Theorem 2: Concentration of Huber's Estimator

First, we control the deviations of Huber's estimator using the deviations of ψ(X -Hub(X n 1 )). We will need the following lemma to control the variance of ψ(X -Hub(X n 1 )), which will in turn allow us to control its deviation with Lemma 8.

Lemma 7 (Controlling Variance of Influence of Huber's Estimator) Suppose that Y 1 , . . . , Y n are i.i.d with law P . Then

Var(ψ(Y -

Lemma 8 (Concentrating Huber's Estimator by Concentrating the Influence) Suppose that X 1 , . . . , X n are i.i.d with law (1 -ε)P + εH for some H ∈ P and proportion of outliers ε ∈ (0, 1/2).

Then, for any η > 0 and λ ∈ (0, β/2], we have

Then, using these Lemmas, we can prove the theorem.

Step 1. For any δ ∈ (0, 1), with probability larger than 1 -3δ,

and ( 4/3 + 1 -1)/(4/3) ≥ 8/7, hence, from Lemma 9, we get the following sufficient condition for Equation (12) to hold:

.

Hence, taking this to the square,

Step 3. Using Lemma 8 and Step 1 prove that the theorem is true. PROOF: The hypotheses of Lemma 8 are verified and we can use its result and together with Equation ( 11) we get with probability larger than 1 -5δ, Let ρ be Huber's loss function, with ψ = ρ ′ . We have that for any x > 0, ψ(x) 2 ≤ 2ρ(x). Hence,

Then, use that by definition of Hub(P ),

and finally, use that ρ(x) ≤ x 2 /2 to conclude.

F.2. Proof of Lemma 8 : Concentrating Huber's Estimator by Concentrating the Influence

For all n ∈ N * , λ > 0, let

where ∆ n = Hub(P ) -Hub(X n 1 ).

From equation ( 13),

Hence, because ψ ′ ∈ [0, 1], we have

The right-hand side depends on the infimum of the mean of n i.i.d random variables in [0, 1]. Hence, the function

satisfies, by sub-linearity of the supremum operator and triangular inequality, the bounded difference property, with differences bounded by 1. Hence, by Hoeffding's inequality, we get with probability larger than 1 -e -2nη 2 ,

and using Hoeffding's inequality to control 1 n n i=1 1{W i = 1}, we have with probability larger

Step 4. For λ ∈ (0, β/2),

PROOF: For any λ > 0, we have

Step 5. We prove that m n ≥ p, and hence

Then, we plug the bound on m n found in the previous step in equation ( 20), we get for any η > 0 and λ ∈ (0, β/2],

Appendix G. Proofs of Auxiliary Lemmas G.1. Proof of Lemma 6

We have,

Remark that the integral is

Then, we compute the integrals. By change of variable u = y/k, we have

and for l = j, In this section we illustrate the impact of the choice of β and ε on the estimation.

Choice of β (Figure 4(b)): The choice of β is a trade-off between the bias (distance |Hub(P ) -E[X]| which decreases as β go to infinity) and robustness (when β goes to 0, Hub(P ) goes to the median). To illustrate this trade-off we use the Weibull distribution for which can be very asymmetric. We use a 3-armed bandit problem with shape parameters (2, 2, 0.75) and scale parameters (0.5, 0.7, 0.8) which implies that the means are approximately (0.44, 0.62, 0.95). These distributions are very asymmetric, hence the bias |Hub(P )-E[X]| is high and in fact even though arm 3 has the optimal mean, arm 2 will have the optimal median, the medians are given by (0.41, 0.58, 0.49).

In this experiment we don't use any corruption as we don't want to complicate the interpretation.

As expected by the theory, we get that β i should not be too small or too large but it should be around 4σ i .

Choice of ε (Figure 4(a)): To illustrate the dependency in ε, we also use the Weibull distribution to show the dependency in ε with the same parameters as in the previous Weibull example, except that we choose β i = 5σ i which is around the optimum found in the previous experiment and we corrupt with 2% of outliers (this is the true ε while we will make the ε used in the definition of the algorithm vary). The outliers are constructed as in Section 5. The effect of the parameter ε is difficult to assess because ε has an impact on the length of force exploration that we impose at the beginning of our algorithm (the s lim ).