Search

Layered semiconductors have recently emerged as capable host materials for novel quantum applications ranging from phonics to sensing. Most studies have focused on artificial layered materials, such as hexagonal boron nitride and transitional dichalcogenides. Natural layered materials, such as talc and other silicates, have remained largely unexplored despite their desirable properties, e.g, wide direct bandgap, low concentration of optically active defects, and low abundance of nuclear spins. In this article, we carry out an extensive computational study on pristine and defected talcum layers and discuss their potential applications. After establishing the properties of bulk talc, we study the electronic structure, charge states, spin and optical properties of vacancy defects, metal, metalloid, and non-metallic impurities. We identify several color centers, electron paramagnetic resonance (EPR) centers, potential spin quantum bits, and dopants. These findings advance our understanding of defected talcum layers and point toward potential applications in quantum technologies.

Pathogens usually exist in heterogeneous variants, like subtypes and strains. Quantifying treatment effects on the different variants is important for guiding prevention policies and treatment development. Here we ground analyses of variant-specific effects on a formal framework for causal inference. This allows us to clarify the interpretation of existing methods and define new estimands. Unlike most of the existing literature, we explicitly consider the (realistic) setting with interference in the target population: even if individuals can be sensibly perceived as iid in randomized trial data, there will often be interference in the target population where treatments, like vaccines, are rolled out. Thus, one of our contributions is to derive explicit conditions guaranteeing that commonly reported vaccine efficacy parameters quantify well-defined causal effects, also in the presence of interference. Furthermore, our results give alternative justifications for reporting estimands on the relative, rather than absolute, scale. We illustrate the findings with an analysis of a large HIV1 vaccine trial, where there is interest in distinguishing vaccine effects on viruses with different genome sequences.

We consider offline reinforcement learning (RL) in $H$-horizon Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where the action-value function of every policy is linear with respect to a given $d$-dimensional feature function. The hope in this setting is that learning a good policy will be possible without requiring a sample size that scales with the number of states in the MDP. Foster et al. [2021] have shown this to be impossible even under $\textit{concentrability}$, a data coverage assumption where a coefficient $C_\text{conc}$ bounds the extent to which the state-action distribution of any policy can veer off the data distribution. However, the data in this previous work was in the form of a sequence of individual transitions. This leaves open the question of whether the negative result mentioned could be overcome if the data was composed of sequences of full trajectories. In this work we answer this question positively by proving that with trajectory data, a dataset of size $\text{poly}(d,H,C_\text{conc})/\epsilon^2$ is sufficient for deriving an $\epsilon$-optimal policy, regardless of the size of the state space. The main tool that makes this result possible is due to Weisz et al. [2023], who demonstrate that linear MDPs can be used to approximate linearly $q^\pi$-realizable MDPs. The connection to trajectory data is that the linear MDP approximation relies on "skipping" over certain states. The associated estimation problems are thus easy when working with trajectory data, while they remain nontrivial when working with individual transitions. The question of computational efficiency under our assumptions remains open.

In automated decision making processes in the online fashion industry, the 'predict-then-optimize' paradigm is frequently applied, particularly for markdown pricing strategies. This typically involves a mixed-integer optimization step, which is crucial for maximizing profit and merchandise volume. In practice, the size and complexity of the optimization problem is prohibitive for using off-the-shelf solvers for mixed integer programs and specifically tailored approaches are a necessity. Our paper introduces specific heuristics designed to work alongside decomposition methods, leading to almost-optimal solutions. These heuristics, which include both primal heuristic methods and a cutting plane generation technique within a Lagrangian decomposition framework, are the core focus of the present paper. We provide empirical evidence for their effectiveness, drawing on real-world applications at Zalando SE, one of Europe's leading online fashion retailers, highlighting the practical value of our work. The contributions of this paper are deeply ingrained into Zalando's production environment to its large-scale catalog ranging in the millions of products and improving weekly profits by millions of Euros.

We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of state-action features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly $q^\pi$-realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly $q^\pi$-realizable MDPs that simultaneously learns what states should be skipped over and runs another learning algorithm on the linear MDP hidden in the problem. The method returns an $\epsilon$-optimal policy after $\text{polylog}(H, d)/\epsilon^2$ interactions with the MDP, where $H$ is the time horizon and $d$ is the dimension of the feature vectors, giving the first polynomial-sample-complexity online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity is shown to degrade gracefully with the misspecification error.

Subscribing to online services is typically a straightforward process, but cancelling them can be arduous and confusing -- causing many to resign and continue paying for services they no longer use. Making the cancellation intentionally difficult is recognized as a dark pattern called Roach Motel. This paper characterizes the subscription and cancellation flows of popular news websites from four different countries, and discusses them in the context of recent regulatory changes. We study the design features that make it difficult to cancel a subscription and find several cancellation flows that feature intentional barriers, such as forcing users to type in a phrase or call a representative. Further, we find many subscription flows that do not adequately inform users about recurring charges. Our results point to a growing need for effective regulation of designs that trick, coerce, or manipulate users into paying for subscriptions they do not want.

While policy optimization algorithms have played an important role in recent empirical success of Reinforcement Learning (RL), the existing theoretical understanding of policy optimization remains rather limited -- they are either restricted to tabular MDPs or suffer from highly suboptimal sample complexity, especial in online RL where exploration is necessary. This paper proposes a simple efficient policy optimization framework -- Optimistic NPG for online RL. Optimistic NPG can be viewed as a simple combination of the classic natural policy gradient (NPG) algorithm [Kakade, 2001] with optimistic policy evaluation subroutines to encourage exploration. For $d$-dimensional linear MDPs, Optimistic NPG is computationally efficient, and learns an $\varepsilon$-optimal policy within $\tilde{O}(d^2/\varepsilon^3)$ samples, which is the first computationally efficient algorithm whose sample complexity has the optimal dimension dependence $\tilde{\Theta}(d^2)$. It also improves over state-of-the-art results of policy optimization algorithms [Zanette et al., 2021] by a factor of $d$. In the realm of general function approximation, which subsumes linear MDPs, Optimistic NPG, to our best knowledge, stands as the first policy optimization algorithm that achieves polynomial sample complexity for learning near-optimal policies.

A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterpart in supervised learning, linear regression, can be solved both statistically and computationally efficiently. Therefore, it was quite surprising when a recent work \cite{kane2022computational} showed a computational-statistical gap for linear reinforcement learning: even though there are polynomial sample-complexity algorithms, unless NP = RP, there are no polynomial time algorithms for this setting. In this work, we build on their result to show a computational lower bound, which is exponential in feature dimension and horizon, for linear reinforcement learning under the Randomized Exponential Time Hypothesis. To prove this we build a round-based game where in each round the learner is searching for an unknown vector in a unit hypercube. The rewards in this game are chosen such that if the learner achieves large reward, then the learner's actions can be used to simulate solving a variant of 3-SAT, where (a) each variable shows up in a bounded number of clauses (b) if an instance has no solutions then it also has no solutions that satisfy more than (1-$\epsilon$)-fraction of clauses. We use standard reductions to show this 3-SAT variant is approximately as hard as 3-SAT. Finally, we also show a lower bound optimized for horizon dependence that almost matches the best known upper bound of $\exp(\sqrt{H})$.

We consider approximate dynamic programming in $\gamma$-discounted Markov decision processes and apply it to approximate planning with linear value-function approximation. Our first contribution is a new variant of Approximate Policy Iteration (API), called Confident Approximate Policy Iteration (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon $H$ and the worst-case approximation error $\epsilon$ of the action-value functions of stationary policies. This improvement over API (whose error scales with $H^2$) comes at the price of an $H$-fold increase in memory cost. Unlike Scherrer and Lesner [2012], who recommended computing a non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and $d$-dimensional linear function approximation. As such, we design a planning algorithm that applies CAPI to obtain a sequence of policies with successively refined accuracies on a dynamically evolving set of states. The algorithm outputs an $\tilde O(\sqrt{d}H\epsilon)$-optimal policy after issuing $\tilde O(dH^4/\epsilon^2)$ queries to the simulator, simultaneously achieving the optimal accuracy bound and the best known query complexity bound, while earlier algorithms in the literature achieve only one of them. This query complexity is shown to be tight in all parameters except $H$. These improvements come at the expense of a mild (polynomial) increase in memory and computational costs of both the algorithm and its output policy.

The Beam Expander Testing X-ray facility (BEaTriX) is a unique X-ray apparatus now operated at the Istituto Nazionale di Astrofisica (INAF), Osservatorio Astronomico di Brera (OAB), in Merate, Italy. It has been specifically designed to measure the point spread function (PSF) and the effective area (EA) of the X-ray mirror modules (MMs) of the Advanced Telescope for High-ENergy Astrophysics (ATHENA), based on silicon pore optics (SPO) technology, for verification before integration into the mirror assembly. To this end, BEaTriX generates a broad, uniform, monochromatic, and collimated X-ray beam at 4.51 keV. [...] In BEaTriX, a micro-focus X-ray source with a titanium anode is placed in the focus of a paraboloidal mirror, which generates a parallel beam. A crystal monochromator selects the 4.51 keV line, which is expanded to the final size by a crystal asymmetrically cut with respect to the crystalline planes. [...] After characterization, the BEaTriX beam has the nominal dimensions of 170 mm x 60 mm, with a vertical divergence of 1.65 arcsec and a horizontal divergence varying between 2.7 and 3.45 arcsec, depending on the monochromator setting: either high collimation or high intensity. The flux per area unit varies from 10 to 50 photons/s/cm2 from one configuration to the other. The BEaTriX beam performance was tested using an SPO MM, whose entrance pupil was fully illuminated by the expanded beam, and its focus was directly imaged onto the camera. The first light test returned a PSF and an EA in full agreement with expectations. As of today, the 4.51 keV beamline of BEaTriX is operational and can characterize modular X-ray optics, measuring their PSF and EA with a typical exposure of 30 minutes. [...] We expect BEaTriX to be a crucial facility for the functional test of modular X-ray optics, such as the SPO MMs for ATHENA., Comment: Accepted on 29 June 2022 for publication in Astronomy & Astrophysics, Sect. 13, Astronomical instrumentation of Astronomy and Astrophysics. Version after language correction

We consider the minimax query complexity of online planning with a generative model in fixed-horizon Markov decision processes (MDPs) with linear function approximation. Following recent works, we consider broad classes of problems where either (i) the optimal value function $v^\star$ or (ii) the optimal action-value function $q^\star$ lie in the linear span of some features; or (iii) both $v^\star$ and $q^\star$ lie in the linear span when restricted to the states reachable from the starting state. Recently, Weisz et al. (2021b) showed that under (ii) the minimax query complexity of any planning algorithm is at least exponential in the horizon $H$ or in the feature dimension $d$ when the size $A$ of the action set can be chosen to be exponential in $\min(d,H)$. On the other hand, for the setting (i), Weisz et al. (2021a) introduced TensorPlan, a planner whose query cost is polynomial in all relevant quantities when the number of actions is fixed. Among other things, these two works left open the question whether polynomial query complexity is possible when $A$ is subexponential in $\min(d,H)$. In this paper we answer this question in the negative: we show that an exponentially large lower bound holds when $A=\Omega(\min(d^{1/4},H^{1/2}))$, under either (i), (ii) or (iii). In particular, this implies a perhaps surprising exponential separation of query complexity compared to the work of Du et al. (2021) who prove a polynomial upper bound when (iii) holds for all states. Furthermore, we show that the upper bound of TensorPlan can be extended to hold under (iii) and, for MDPs with deterministic transitions and stochastic rewards, also under (ii).

We consider local planning in fixed-horizon MDPs with a generative model under the assumption that the optimal value function lies close to the span of a feature map. The generative model provides a local access to the MDP: The planner can ask for random transitions from previously returned states and arbitrary actions, and features are only accessible for states that are encountered in this process. As opposed to previous work (e.g. Lattimore et al. (2020)) where linear realizability of all policies was assumed, we consider the significantly relaxed assumption of a single linearly realizable (deterministic) policy. A recent lower bound by Weisz et al. (2020) established that the related problem when the action-value function of the optimal policy is linearly realizable requires an exponential number of queries, either in $H$ (the horizon of the MDP) or $d$ (the dimension of the feature mapping). Their construction crucially relies on having an exponentially large action set. In contrast, in this work, we establish that poly$(H,d)$ planning is possible with state value function realizability whenever the action set has a constant size. In particular, we present the TensorPlan algorithm which uses poly$((dH/\delta)^A)$ simulator queries to find a $\delta$-optimal policy relative to any deterministic policy for which the value function is linearly realizable with some bounded parameter. This is the first algorithm to give a polynomial query complexity guarantee using only linear-realizability of a single competing value function. Whether the computation cost is similarly bounded remains an open question. We extend the upper bound to the near-realizable case and to the infinite-horizon discounted setup. We also present a lower bound in the infinite-horizon episodic setting: Planners that achieve constant suboptimality need exponentially many queries, either in $d$ or the number of actions.

The Secured Overnight Funding Rate (SOFR) is becoming the main Risk-Free Rate benchmark in US dollars, thus interest rate term structure models need to be updated to reflect the key features exhibited by the dynamics of SOFR and the forward rates implied by SOFR futures. Historically, interest rate term structure modelling has been based on rates of substantially longer time to maturity than overnight, but with SOFR the overnight rate now is the primary market observable. This means that the empirical idiosyncrasies of the overnight rate cannot be ignored when constructing interest rate models in a SOFR-based world. As a rate reflecting transactions in the Treasury overnight repurchase market, the dynamics of SOFR are closely linked to the dynamics of the Effective Federal Funds Rate (EFFR), which is the interest rate most directly impacted by US monetary policy target rate decisions. Therefore, these rates feature jumps at known times (Federal Open Market Committee meeting dates), and market expectations of these jumps are reflected in prices for futures written on these rates. On the other hand, forward rates implied by Fed Funds and SOFR futures continue to evolve diffusively. The model presented in this paper reflects the key empirical features of SOFR dynamics and is calibrated to futures prices. In particular, the model reconciles diffusive forward rate dynamics with piecewise constant paths of the target short rate.

We are interested in understanding whether retrieval-based localization approaches are good enough in the context of self-driving vehicles. Towards this goal, we introduce Pit30M, a new image and LiDAR dataset with over 30 million frames, which is 10 to 100 times larger than those used in previous work. Pit30M is captured under diverse conditions (i.e., season, weather, time of the day, traffic), and provides accurate localization ground truth. We also automatically annotate our dataset with historical weather and astronomical data, as well as with image and LiDAR semantic segmentation as a proxy measure for occlusion. We benchmark multiple existing methods for image and LiDAR retrieval and, in the process, introduce a simple, yet effective convolutional network-based LiDAR retrieval method that is competitive with the state of the art. Our work provides, for the first time, a benchmark for sub-metre retrieval-based localization at city scale. The dataset, its Python SDK, as well as more information about the sensors, calibration, and metadata, are available on the project website: https://pit30m.github.io/, Comment: Published at IROS 2020

We consider the problem of local planning in fixed-horizon and discounted Markov Decision Processes (MDPs) with linear function approximation and a generative model under the assumption that the optimal action-value function lies in the span of a feature map that is available to the planner. Previous work has left open the question of whether there exist sound planners that need only poly(H,d) queries regardless of the MDP, where H is the horizon and d is the dimensionality of the features. We answer this question in the negative: we show that any sound planner must query at least $\min(\exp({\Omega}(d)), {\Omega}(2^H))$ samples in the fized-horizon setting and $\exp({\Omega}(d))$ samples in the discounted setting. We also show that for any ${\delta}>0$, the least-squares value iteration algorithm with $O(H^5d^{H+1}/{\delta}^2)$ queries can compute a ${\delta}$-optimal policy in the fixed-horizon setting. We discuss implications and remaining open questions.

The construction by Du et al. (2019) implies that even if a learner is given linear features in $\mathbb R^d$ that approximate the rewards in a bandit with a uniform error of $\epsilon$, then searching for an action that is optimal up to $O(\epsilon)$ requires examining essentially all actions. We use the Kiefer-Wolfowitz theorem to prove a positive result that by checking only a few actions, a learner can always find an action that is suboptimal with an error of at most $O(\epsilon \sqrt{d})$. Thus, features are useful when the approximation error is small relative to the dimensionality of the features. The idea is applied to stochastic bandits and reinforcement learning with a generative model where the learner has access to $d$-dimensional linear features that approximate the action-value functions for all policies to an accuracy of $\epsilon$. For linear bandits, we prove a bound on the regret of order $\sqrt{dn \log(k)} + \epsilon n \sqrt{d} \log(n)$ with $k$ the number of actions and $n$ the horizon. For RL we show that approximate policy iteration can learn a policy that is optimal up to an additive error of order $\epsilon \sqrt{d}/(1 - \gamma)^2$ and using $d/(\epsilon^2(1 - \gamma)^4)$ samples from a generative model. These bounds are independent of the finer details of the features. We also investigate how the structure of the feature set impacts the tradeoff between sample complexity and estimation error., Comment: 13 pages

We study algorithms for average-cost reinforcement learning problems with value function approximation. Our starting point is the recently proposed POLITEX algorithm, a version of policy iteration where the policy produced in each iteration is near-optimal in hindsight for the sum of all past value function estimates. POLITEX has sublinear regret guarantees in uniformly-mixing MDPs when the value estimation error can be controlled, which can be satisfied if all policies sufficiently explore the environment. Unfortunately, this assumption is often unrealistic. Motivated by the rapid growth of interest in developing policies that learn to explore their environment in the lack of rewards (also known as no-reward learning), we replace the previous assumption that all policies explore the environment with that a single, sufficiently exploring policy is available beforehand. The main contribution of the paper is the modification of POLITEX to incorporate such an exploration policy in a way that allows us to obtain a regret guarantee similar to the previous one but without requiring that all policies explore environment. In addition to the novel theoretical guarantees, we demonstrate the benefits of our scheme on environments which are difficult to explore using simple schemes like dithering. While the solution we obtain may not achieve the best possible regret, it is the first result that shows how to control the regret in the presence of function approximation errors on problems where exploration is nontrivial. Our approach can also be seen as a way of reducing the problem of minimizing the regret to learning a good exploration policy. We believe that modular approaches like ours can be highly beneficial in tackling harder control problems.

In this paper we propose a novel semantic localization algorithm that exploits multiple sensors and has precision on the order of a few centimeters. Our approach does not require detailed knowledge about the appearance of the world, and our maps require orders of magnitude less storage than maps utilized by traditional geometry- and LiDAR intensity-based localizers. This is important as self-driving cars need to operate in large environments. Towards this goal, we formulate the problem in a Bayesian filtering framework, and exploit lanes, traffic signs, as well as vehicle dynamics to localize robustly with respect to a sparse semantic map. We validate the effectiveness of our method on a new highway dataset consisting of 312km of roads. Our experiments show that the proposed approach is able to achieve 0.05m lateral accuracy and 1.12m longitudinal accuracy on average while taking up only 0.3% of the storage required by previous LiDAR intensity-based approaches., Comment: 8 pages, 4 figures, 4 tables, 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2019)

Reliable and accurate lane detection has been a long-standing problem in the field of autonomous driving. In recent years, many approaches have been developed that use images (or videos) as input and reason in image space. In this paper we argue that accurate image estimates do not translate to precise 3D lane boundaries, which are the input required by modern motion planning algorithms. To address this issue, we propose a novel deep neural network that takes advantage of both LiDAR and camera sensors and produces very accurate estimates directly in 3D space. We demonstrate the performance of our approach on both highways and in cities, and show very accurate estimates in complex scenarios such as heavy traffic (which produces occlusion), fork, merges and intersections., Comment: IEEE International Conference on Intelligent Robots and Systems (IROS) 2018