Search

Existing performance measures for bandit algorithms such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the play of an arbitrarily bad arm at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger performance measure, the uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of bandit algorithms. Specifically, ULI characterizes the instantaneous performance since it ensures that the per-round regret of the played arm is bounded by a function, monotonically decreasing w.r.t. (large) round t, preventing revisits to bad arms when sufficient samples are available. We demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned performance measures. To examine the achievability of ULI in the finite arm setting, we first provide two positive results that some elimination-based algorithms and high-probability adversarial algorithms with stronger analysis or additional designs, can attain near-optimal ULI guarantees. Then, we also provide a negative result, indicating that optimistic algorithms cannot achieve a near-optimal ULI guarantee. Finally, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULI guarantee, given access to an optimization oracle.

Existing online learning algorithms for adversarial Markov Decision Processes achieve ${O}(\sqrt{T})$ regret after $T$ rounds of interactions even if the loss functions are chosen arbitrarily by an adversary, with the caveat that the transition function has to be fixed. This is because it has been shown that adversarial transition functions make no-regret learning impossible. Despite such impossibility results, in this work, we develop algorithms that can handle both adversarial losses and adversarial transitions, with regret increasing smoothly in the degree of maliciousness of the adversary. More concretely, we first propose an algorithm that enjoys $\widetilde{{O}}(\sqrt{T} + C^{\textsf{P}})$ regret where $C^{\textsf{P}}$ measures how adversarial the transition functions are and can be at most ${O}(T)$. While this algorithm itself requires knowledge of $C^{\textsf{P}}$, we further develop a black-box reduction approach that removes this requirement. Moreover, we also show that further refinements of the algorithm not only maintains the same regret bound, but also simultaneously adapts to easier environments (where losses are generated in a certain stochastically constrained manner as in Jin et al. [2021]) and achieves $\widetilde{{O}}(U + \sqrt{UC^{\textsf{L}}} + C^{\textsf{P}})$ regret, where $U$ is some standard gap-dependent coefficient and $C^{\textsf{L}}$ is the amount of corruption on losses., Comment: Update the camera-ready version for NeurIPS 2023

Tianwen-1 spacecraft (Wan et al. 2020) is China's first Mars exploration mission. The Mars Orbiter Magnetometer (MOMAG) is a scientific instrument aboard the Tianwen-1 mission that is designed to study magnetic fields at Mars, including the solar wind to the magnetosheath and the ionosphere. Using the first Tianwen-1/MOMAG data that is publicly available, we present interplanetary coronal mass ejection (ICME) and stream interaction region (SIR) catalogues based on in-situ observations at Mars between November 16, 2021, and December 31, 2021. We compared the magnetic field intensity and vector magnetic field measurements from Tianwen-1/MOMAG and Mars Atmospheric Volatile EvolutioN (MAVEN)/MAG during the ICME and SIR interval and found a generally good consistency between them. Due to MAVEN's orbital adjustment since 2019, the Tianwen-1/MOMAG instrument is currently the almost unique interplanetary magnetic field monitor at Mars. The observations indicate that the MOMAG instrument on Tianwen-1 is performing well and can provide accurate measurements of the vector magnetic field in the near-Mars solar wind space. The multi-point observations combining MOMAG, MINPA, and MEPA on board Tianwen-1 with MAG, SWIA, and STATIC on board MAVEN will open a window to systematically study the characteristic of ICMEs and SIRs at Mars, and their influences on the Martian atmosphere and ionosphere.

We study the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simultaneously (often known as a best-of-both-world guarantee). A line of recent works shows that when configured and analyzed properly, the Follow-the-Regularized-Leader (FTRL) algorithm, originally designed for the adversarial setting, can in fact optimally adapt to the stochastic setting as well. Such results, however, critically rely on an assumption that there exists one unique optimal arm. Recently, Ito (2021) took the first step to remove such an undesirable uniqueness assumption for one particular FTRL algorithm with the $\frac{1}{2}$-Tsallis entropy regularizer. In this work, we significantly improve and generalize this result, showing that uniqueness is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. For some regularizers, our regret bounds also improve upon prior results even when uniqueness holds. We further provide an application of our results to the decoupled exploration and exploitation problem, demonstrating that our techniques are broadly applicable., Comment: Update the camera-ready version for NeurIPS 2023

In two-dimensional materials, structure difference induces the difference in phonon dispersions, leading to the anisotropy of in-plane thermal transport. Here, we report an exceptional case in layered PdSe2, where the bonding, force constants, and lattice constants are nearly-equal along the in-plane crystallographic axis directions. The phonon dispersions show significant differences between the Gamma-X and Gamma-Y directions, leading to the anisotropy of in-plane thermal conductivity with a ratio up to 1.8. Such anisotropy is not only unexpected in equilaterally structured (in-plane) materials but also comparable to the record in the non-equilaterally structured material reported to date. By combining inelastic X-ray scattering and first-principles calculations, we attribute such anisotropy to the low-energy phonons along Gamma-X, in particular, their lower group velocities and "avoided-crossing" behavior. The different bucking structures between a- (zigzag-type) and b-axis (flat-type) are mainly responsible for the unique phonon dynamics properties of PdSe2. The present results illustrate the unusual thermal conduction mechanism of the equilaterally structured materials and provide valuable insights on thermal management in electronic devices., Comment: 16 figures, 2 tables

We study the problem of stochastic bandits with adversarial corruptions in the cooperative multi-agent setting, where $V$ agents interact with a common $K$-armed bandit problem, and each pair of agents can communicate with each other to expedite the learning process. In the problem, the rewards are independently sampled from distributions across all agents and rounds, but they may be corrupted by an adversary. Our goal is to minimize both the overall regret and communication cost across all agents. We first show that an additive term of corruption is unavoidable for any algorithm in this problem. Then, we propose a new algorithm that is agnostic to the level of corruption. Our algorithm not only achieves near-optimal regret in the stochastic setting, but also obtains a regret with an additive term of corruption in the corrupted setting, while maintaining efficient communication. The algorithm is also applicable for the single-agent corruption problem, and achieves a high probability regret that removes the multiplicative dependence of $K$ on corruption level. Our result of the single-agent case resolves an open question from Gupta et al. [2019].

Scanning tunneling spectroscopy (STS) has yielded significant insight on the electronic structure of graphene and other two-dimensional (2D) materials. STS directly measures a fundamental and directly calculable quantity: the single particle density of states (SPDOS). Due to experimental setup limitations, however, STS has been unable to explore 2D materials in ultra-high magnetic fields where electron-electron interactions can drastically change the SPDOS. Recent developments in the assembly of heterostructures composed of graphene and hexagonal boron nitride have enabled a device-based alternative to potentially overcome these roadblocks. Thus far, however, these nascent efforts are incomplete in analyzing and understanding tunneling spectra and have yet to explore graphene at high magnetic fields. Here we report an experiment at magnetic fields up to 18 T that uses graphene tunneling field effect transistors (TFETs) to establish a clear benchmark for measurement and analysis of graphene planar tunneling spectroscopy. We acquire gate tunable tunneling spectra of graphene and then use these data and electrostatic arguments to develop a systematic analysis scheme. This analysis reveals that TFET devices directly probe electronic structure features near and far from the Fermi level. In particular, our study yields identification of the Dirac point and numerous Landau levels as they fill and empty with charge via application of a gate voltage. Our work demonstrates that TFET devices are a viable platform for directly probing the electronic structure of graphene and other 2D materials in high magnetic fields, where novel electronic states emerge.

This paper considers the problem of robustly estimating the parameters of a heavy-tailed multivariate distribution when the covariance matrix is known to have the structure of a low-rank matrix plus a diagonal matrix as considered in factor analysis (FA). By assuming the observed data to follow the multivariate Student's t distribution, we can robustly estimate the parameters via maximum likelihood estimation (MLE). However, the MLE of parameters becomes an intractable problem when the multivariate Student's t distribution and the FA structure are both introduced. In this paper, we propose an algorithm based on the generalized expectation maximization (GEM) method to obtain estimators. The robustness of our proposed method is further enhanced to cope with missing values. Finally, we show the performance of our proposed algorithm using both synthetic data and real financial data., Comment: Presented at Eurocast 2019

The autoregressive (AR) model is a widely used model to understand time series data. Traditionally, the innovation noise of the AR is modeled as Gaussian. However, many time series applications, for example, financial time series data, are non-Gaussian, therefore, the AR model with more general heavy-tailed innovations is preferred. Another issue that frequently occurs in time series is missing values, due to system data record failure or unexpected data loss. Although there are numerous works about Gaussian AR time series with missing values, as far as we know, there does not exist any work addressing the issue of missing data for the heavy-tailed AR model. In this paper, we consider this issue for the first time, and propose an efficient framework for parameter estimation from incomplete heavy-tailed time series based on a stochastic approximation expectation maximization (SAEM) coupled with a Markov Chain Monte Carlo (MCMC) procedure. The proposed algorithm is computationally cheap and easy to implement. The convergence of the proposed algorithm to a stationary point of the observed data likelihood is rigorously proved. Extensive simulations and real datasets analyses demonstrate the efficacy of the proposed framework., Comment: This is a companion document to a paper that is accepted to IEEE Transaction on Signal Processing 2019, complemented with the supplementary material