1 January 2023 in Operations Research
As a result of digitization of the economy, more and more decision makers from a wide range of domains have gained the ability to target products, services, and information provision based on individual characteristics. Examples include selecting offers, prices, advertisements, or emails to send to consumers, choosing a bid to submit in a contextual first-price auctions, and determining which medication to prescribe to a patient. The key to enabling this is to learn a treatment policy from historical observational data in a sample-efficient way, hence uncovering the best personalized treatment choice recommendation. In “Offline Policy Learning: Generalization and Optimization,” Z. Zhou, S. Athey, and S. Wager provide a sample-optimal policy learning algorithm that is computationally efficient and that learns a tree-based treatment policy from observational data. In our quest toward fully automated personalization, the work provides a theoretically sound and practically implementable approach.
16 July 2019 in IEEE Transactions on Pattern Analysis and Machine Intelligence
Low-rank tensor recovery in the presence of sparse but arbitrary errors is an important problem with many practical applications. In this work, we propose a general framework that recovers low-rank tensors, in which the data can be deformed by some unknown transformations and corrupted by arbitrary sparse errors. We give a unified presentation of the surrogate-based formulations that incorporate the features of rectification and alignment simultaneously, and establish worst-case error bounds of the recovered tensor. In this context, the state-of-the-art methods ‘RASL’ and ‘TILT’ can be viewed as two special cases of our work, and yet each only performs part of the function of our method. Subsequently, we study the optimization aspects of the problem in detail by deriving two algorithms, one based on the alternating direction method of multipliers (ADMM) and the other based on proximal gradient. We provide convergence guarantees for the latter algorithm, and demonstrate the performance of the former through in-depth simulations. Finally, we present extensive experimental results on public datasets to demonstrate the effectiveness and efficiency of the proposed framework and algorithms.
20 November 2017 in IEEE Transactions on Automatic Control
Inverse reinforcement learning (IRL) attempts to use demonstrations of “expert” decision making in a Markov decision process to infer a corresponding policy that shares the “structured, purposeful” qualities of the expert's actions. In this paper, we extend the maximum causal entropy framework, a notable paradigm in IRL, to the infinite time horizon setting. We consider two formulations (maximum discounted causal entropy and maximum average causal entropy) appropriate for the infinite horizon case and show that both result in optimization programs that can be reformulated as convex optimization problems, thus admitting efficient computation. We then develop a gradient based algorithm for the maximum discounted causal entropy formulation that enjoys the desired feature of being model agnostic, a property that is absent in many previous IRL algorithms. We propose the stationary soft Bellman policy, a key building block in the gradient based algorithm, and study its properties in depth, which not only leads to theoretical insight into its analytical properties, but also helps motivate a large toolkit of methods for implementing the gradient based algorithm. Finally, we select three
1 January 2025 in Operations Research
In “Optimal No-Regret Learning in Repeated First-Price Auctions,” Y. Han, W. Tsachy, and Z. Zhou study online learning in repeated first-price auctions where a bidder, only observing the winning bid at the end of each auction, learns to adaptively bid to maximize her cumulative payoff. To achieve this goal, the bidder faces censored feedback: If she wins the bid, then she is not able to observe the highest bid of the other bidders, which we assume is i.i.d. drawn from an unknown distribution. In this paper, they develop the first learning algorithm that achieves a near-optimal regret bound, by exploiting two structural properties of first-price auctions, that is, the specific feedback structure and payoff function.
23 December 2015 in IEEE Transactions on Automatic Control
Chance constrained methods handle problem uncertainty by formulating the constraints probabilistically and only guaranteeing their satisfaction up to a given violation level. This paper extends existing chance constrained methods to handle both uncertainty in the system state as well as in the constraint parameters. Due to the imperfect knowledge of the system state caused by motion, sensor and environment uncertainty, the system constraints cannot be guaranteed to be satisfied and consequently must be considered probabilistically. Prior work has primarily only dealt with uncertainty in the system state or constraint parameters but not both simultaneously, however, in many motivating applications both frequently occur. To handle this case, previous approaches either approximate the distribution leading to a nonconvex optimization program, or use sampling alone to represent the uncertainty which requires a large number of samples to accurately represent the distribution. To address these limitations, a novel hybrid method is proposed that uses both analytical functions and sampling to represent the uncertainty. It is shown that under certain conditions, the resulting optimization program using this hybrid representation is convex. To check the convexity, an efficient a priori, sufficient condition is developed. Furthermore, by using this hybrid representation, this method drastically reduces the computational complexity over previous methods, which is demonstrated through two examples. Consequently, this method has the ability to enable real-time stochastic control for the motivating applications.
1 October 2023 in Management Science
Policy learning using historical observational data are an important problem that has widespread applications. Examples include selecting offers, prices, or advertisements for consumers; choosing bids in contextual first-price auctions; and selecting medication based on patients’ characteristics. However, existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment that has generated the data: an assumption that is often false or too coarse an approximation. In this paper, we lift this assumption and aim to learn a distributionally robust policy with incomplete observational data. We first present a policy evaluation procedure that allows us to assess how well the policy does under worst-case environment shift. We then establish a central limit theorem type guarantee for this proposed policy evaluation scheme. Leveraging this evaluation scheme, we further propose a novel learning algorithm that is able to learn a policy that is robust to adversarial perturbations and unknown covariate shifts with a performance guarantee based on the theory of uniform convergence. Finally, we empirically test the effectiveness of our proposed algorithm in synthetic datasets and demonstrate that it provides the robustness that is missing using standard policy learning algorithms. We conclude the paper by providing a comprehensive application of our methods in the context of a real-world voting data set.This paper was accepted by Hamid Nazerzadeh, data science.Funding: This work was supported by the National Science Foundation [Grant CCF-2106508] and the Air Force Office of Scientific Research [Award FA9550-20-1-0397]. Z. Zhou also gratefully acknowledges the JP Morgan AI Research Grant and the New York University’s Center for Global Economy and Business faculty research grant for support on this work. Additional support is gratefully acknowledged from the National Science Foundation [Grants 1915967 and 2118199].Supplemental Material: The data files and online appendix are available at https://doi.org/10.1287/mnsc.2023.4678 .