Jia Yuan Yu

UAI Conference 2021 Conference Paper

Bias-corrected peaks-over-threshold estimation of the CVaR

• Dylan Troop
• Frédéric Godin
• Jia Yuan Yu

The conditional value-at-risk (CVaR) is a useful risk measure in fields such as machine learning, finance, insurance, energy, etc. When measuring very extreme risk, the commonly used CVaR estimation method of sample averaging does not work well due to limited data above the value-at-risk (VaR), the quantile corresponding to the CVaR level. To mitigate this problem, the CVaR can be estimated by extrapolating above a lower threshold than the VaR using a generalized Pareto distribution (GPD), which is often referred to as the peaks-over-threshold (POT) approach. This method often requires a very high threshold to fit well, leading to high variance in estimation, and can induce significant bias if the threshold is chosen too low. In this paper, we address this bias-variance tradeoff by deriving a new expression for the GPD approximation error of the CVaR, a bias term induced by the choice of threshold, as well as a bias correction method for the estimated GPD parameters. This leads to the derivation of a new CVaR estimator that is asymptotically unbiased and less sensitive to lower thresholds being used. An asymptotic confidence interval for the estimator is also constructed. In a practical setting, we show through experiments that our estimator provides a significant performance improvement compared with competing CVaR estimators in finite samples from heavy-tailed distributions.

AAAI Conference 2019 Conference Paper

State-Augmentation Transformations for Risk-Sensitive Reinforcement Learning

• Shuai Ma
• Jia Yuan Yu

In the framework of MDP, although the general reward function takes three arguments—current state, action, and successor state; it is often simplified to a function of two arguments—current state and action. The former is called a transition-based reward function, whereas the latter is called a state-based reward function. When the objective involves the expected total reward only, this simplification works perfectly. However, when the objective is risk-sensitive, this simplification leads to an incorrect value. We propose three successively more general state-augmentation transformations (SATs), which preserve the reward sequences as well as the reward distributions and the optimal policy in risk-sensitive reinforcement learning. In risk-sensitive scenarios, firstly we prove that, for every MDP with a stochastic transition-based reward function, there exists an MDP with a deterministic state-based reward function, such that for any given (randomized) policy for the first MDP, there exists a corresponding policy for the second MDP, such that both Markov reward processes share the same reward sequence. Secondly we illustrate that two situations require the proposed SATs in an inventory control problem. One could be using Q-learning (or other learning methods) on MDPs with transition-based reward functions, and the other could be using methods, which are for the Markov processes with a deterministic state-based reward functions, on the Markov processes with general reward functions. We show the advantage of the SATs by considering Value-at-Risk as an example, which is a risk measure on the reward distribution instead of the measures (such as mean and variance) of the distribution. We illustrate the error in the reward distribution estimation from the reward simplification, and show how the SATs enable a variance formula to work on Markov processes with general reward functions.

TCS Journal 2014 Journal Article

Adaptive and optimal online linear regression on ℓ 1 -balls

• Sébastien Gerchinovitz
• Jia Yuan Yu

We consider the problem of online linear regression on individual sequences. The goal in this paper is for the forecaster to output sequential predictions which are, after T time rounds, almost as good as the ones output by the best linear predictor in a given ℓ 1 -ball in R d. We consider both the cases where the dimension d is small and large relative to the time horizon T. We first present regret bounds with optimal dependencies on d, T, and on the sizes U, X and Y of the ℓ 1 -ball, the input data and the observations. The minimax regret is shown to exhibit a regime transition around the point d = T U X / ( 2 Y ). Furthermore, we present efficient algorithms that are adaptive, i. e. , that do not require the knowledge of U, X, Y, and T, but still achieve nearly optimal regret bounds.

NeurIPS Conference 2013 Conference Paper

Data-driven Distributionally Robust Polynomial Optimization

• Martin Mevissen
• Emanuele Ragnoli
• Jia Yuan Yu

We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i. e. , it is data-driven and random. Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints. However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder. We show that the solution to the distributionally robust problem is the limit of a sequence of tractable semidefinite programming relaxations. We also give finite-sample consistency guarantees for the data-driven uncertainty sets. Finally, we apply our model and solution method in a water network problem.

IJCAI Conference 2013 Conference Paper

Sample Complexity of Risk-Averse Bandit-Arm Selection

• Jia Yuan Yu
• Evdokia Nikolova

We consider stochastic multiarmed bandit problems where each arm generates i. i. d. rewards according to an unknown distribution. Whereas classical bandit solutions only maximize the expected reward, we consider the problem of minimizing risk using notions such as the value-at-risk, the average value-at-risk, and the mean-variance risk. We present algorithms to minimize the risk over a single and multiple time periods, along with PAC accuracy guarantees given a finite number of reward samples. In the single-period case, we show that finding the arm with least risk requires not many more samples than the arm with highest expected reward. Although minimizing the multiperiod value-at-risk is known to be hard, we present an algorithm with comparable sample complexity under additional assumptions.

EWRL Workshop 2013 Workshop Paper

Towards Active Crowdsourcing for Smart Cities

• François Schnitzler
• Jia Yuan Yu
• Shie Mannor

ICML Conference 2011 Conference Paper

Unimodal Bandits

• Jia Yuan Yu
• Shie Mannor

JMLR Journal 2009 Journal Article

Online Learning with Sample Path Constraints

• Shie Mannor
• John N. Tsitsiklis
• Jia Yuan Yu

We study online learning where a decision maker interacts with Nature with the objective of maximizing her long-term average reward subject to some sample path average constraints. We define the reward-in-hindsight as the highest reward the decision maker could have achieved, while satisfying the constraints, had she known Nature's choices in advance. We show that in general the reward-in-hindsight is not attainable. The convex hull of the reward-in-hindsight function is, however, attainable. For the important case of a single constraint, the convex hull turns out to be the highest attainable function. Using a calibrated forecasting rule, we provide an explicit strategy that attains this convex hull. We also measure the performance of heuristic methods based on non-calibrated forecasters in experiments involving a CPU power management problem. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

ICML Conference 2009 Conference Paper

Piecewise-stationary bandit problems with side observations

• Jia Yuan Yu
• Shie Mannor

EWRL Workshop 2008 Conference Paper

Markov Decision Processes with Arbitrary Reward Processes

• Jia Yuan Yu
• Shie Mannor
• Nahum Shimkin

Abstract We consider a control problem where the decision maker interacts with a standard Markov decision process with the exception that the reward functions vary arbitrarily over time. We extend the notion of Hannan consistency to this setting, showing that, in hindsight, the agent can perform almost as well as every deterministic policy. We present efficient online algorithms in the spirit of reinforcement learning that ensure that the agent’s performance loss, or regret, vanishes over time, provided that the environment is oblivious to the agent’s actions. However, counterexamples indicate that the regret does not vanish if the environment is not oblivious.