Efficient minimax strategies for square loss games

We consider online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and its generalization, the squared Mahalanobis distance. We derive the minimax solutions for the case where the prediction and action spaces are the simplex (this setup is sometimes called the Brier game) and the \ell_2 ball (this setup is related to Gaussian density estimation). We show that in both cases the value of each sub-game is a quadratic function of a simple statistic of the state, with coefficients that can be efficiently computed using an explicit recurrence relation. The resulting deterministic minimax strategy and randomized maximin strategy are linear functions of the statistic.

Online hidden Markov model parameter estimation and minimax robust quickest change detection in uncertain stochastic processes

Stochastic (or random) processes are inherent to numerous fields of human endeavour including engineering, science, and business and finance. This thesis presents multiple novel methods for quickly detecting and estimating uncertainties in several important classes of stochastic processes. The significance of these novel methods is demonstrated by employing them to detect aircraft manoeuvres in video signals in the important application of autonomous mid-air collision avoidance.

A Minimax Filter for Systems with Large Plant Uncertainties Using Measurements Corrupted by Colored Noise

A minimax filter is derived to estimate the state of a system, using observations corrupted by colored noise, when large uncertainties in the plant dynamics and process noise are presen.

Constrained linear minimax filter for systems with large plant uncertainties

This paper presents a method of designing a minimax filter in the presence of large plant uncertainties and constraints on the mean squared values of the estimates. The minimax filtering problem is reformulated in the framework of a deterministic optimal control problem and the method of solution employed, invokes the matrix Minimum Principle. The constrained linear filter and its relation to singular control problems has been illustrated. For the class of problems considered here it is shown that the filter can he constrained separately after carrying out the mini maximization. Numorieal examples are presented to illustrate the results.

Surrogate Regret Bounds for Bipartite Ranking via Strongly Proper Losses

The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. A dominant theoretical and algorithmic framework for the problem has been to reduce bipartite ranking to pairwise classification; in particular, it is well known that the bipartite ranking regret can be formulated as a pairwise classification regret, which in turn can be upper bounded using usual regret bounds for classification problems. Recently, Kotlowski et al. (2011) showed regret bounds for bipartite ranking in terms of the regret associated with balanced versions of the standard (non-pairwise) logistic and exponential losses. In this paper, we show that such (non-pairwise) surrogate regret bounds for bipartite ranking can be obtained in terms of a broad class of proper (composite) losses that we term as strongly proper. Our proof technique is much simpler than that of Kotlowski et al. (2011), and relies on properties of proper (composite) losses as elucidated recently by Reid and Williamson (2010, 2011) and others. Our result yields explicit surrogate bounds (with no hidden balancing terms) in terms of a variety of strongly proper losses, including for example logistic, exponential, squared and squared hinge losses as special cases. An important consequence is that standard algorithms minimizing a (non-pairwise) strongly proper loss, such as logistic regression and boosting algorithms (assuming a universal function class and appropriate regularization), are in fact consistent for bipartite ranking; moreover, our results allow us to quantify the bipartite ranking regret in terms of the corresponding surrogate regret. We also obtain tighter surrogate bounds under certain low-noise conditions via a recent result of Clemencon and Robbiano (2011).

Sequential anomaly detection in the presence of noise and limited feedback

This paper describes a methodology for detecting anomalies from sequentially observed and potentially noisy data. The proposed approach consists of two main elements: 1) filtering, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations and 2) hedging, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on the available feedback from an end user. Our algorithms, which combine universal prediction with recent work on online convex programming, do not require computing posterior distributions given all current observations and involve simple primal-dual parameter updates. At the heart of the proposed approach lie exponential-family models which can be used in a wide variety of contexts and applications, and which yield methods that achieve sublinear per-round regret against both static and slowly varying product distributions with marginals drawn from the same exponential family. Moreover, the regret against static distributions coincides with the minimax value of the corresponding online strongly convex game. We also prove bounds on the number of mistakes made during the hedging step relative to the best offline choice of the threshold with access to all estimated beliefs and feedback signals. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality, as well as on the Enron email dataset. © 1963-2012 IEEE.

Regret as autobiographical memory

We apply all autobiographical memory framework to the Study of regret. Focusing oil the distinction between regrets for specific and general events we argue that the temporal profile of regret, usually explained in terms of the action-inaction distinction, is predicted by models of autobiographical memory. In two studies involving Participants in their sixties we demonstrate a reminiscence bump for general, but not for specific regrets. Recent regrets were more likely to be specific than general in nature. Coding regrets as actions/inactions revealed that general regrets were significantly more likely to be due to inaction while specific regrets were as likely to be clue to action as to inaction. In Study 2 we also generalised all of these findings to a group of participants in their 40s. We re-interpret existing accounts of the temporal profile of regret within the autobiographical memory framework, and Outline the practical and theoretical advantages Of Our memory-based distinction over traditional decision-making approaches to the Study of regret. (C) 2008 Elsevier Inc. All rights reserved.

Comparisons, mental models, and the action effect in judgments of regret

People tend to attribute more regret to a character who has decided to take action and experienced a negative outcome than to one who has decided not to act and experienced a negative outcome. For some decisions, however, this finding is not observed in a between-participants design and thus appears to rely on comparisons between people's representations of action and their representations of inaction. In this article, we outline a mental models account that explains findings from studies that have used within- and between-participants designs, and we suggest that, for decisions with uncertain counterfactual outcomes, information about the consequences of a decision to act causes people to flesh out their representation of the counterfactual states of affairs for inaction. In three experiments, we confirm our predictions about participants' fleshing out of representations, demonstrating that an action effect occurs only when information about the consequences of action is available to participants as they rate the nonactor and when this information about action is informative with respect to judgments about inaction. It is important to note that the action effect always occurs when the decision scenario specifies certain counterfactual outcomes. These results suggest that people sometimes base their attributions of regret on comparisons among different sets of mental models.

Is regret for inaction relatively self-enhancing?

Previous accounts of regret suggest that people report greater regret for inaction than for action because the former is longer lasting and more painful than the latter. We suggest instead that the tendency for people's greatest regrets to concern inaction more than action may be due to the relatively self-enhancing nature of regrets for inaction. In Study I we asked people to think about their greatest recent regret and to code it as being due to action or inaction. In Study 2 participants described their greatest regret from across their entire life. In both studies we observed an inaction effect only amongst individuals high in self-esteem (HSE). In Study 2 we found that the inaction effect was confined to HSE people whose greatest regret was personal in nature. These results support the claim that regret for inaction is relatively self-enhancing and suggest that the inaction effect found in real-life regrets may be due, in part at least, to the self-enhancement goals of HSE individuals. Copyright (c) 2005 John Wiley & Sons, Ltd.

The development of regret

In two experiments, 4- to 9-year-olds played a game in which they
selected one of two boxes to win a prize. On regret trials the unchosen
box contained a better prize than the prize children actually
won, and on baseline trials the other box contained a prize of the
same value. Children rated their feelings about their prize before
and after seeing what they could have won if they had chosen
the other box and were asked to provide an explanation if their
feelings had changed. Patterns of responding suggested that regret
was experienced by 6 or 7 years of age; children of this age could
also explain why they felt worse in regret trials by referring to
the counterfactual situation in which the prize was better. No evidence
of regret was found in 4- and 5-year-olds. Additional findings
suggested that by 6 or 7 years, children’s emotions were
determined by a consideration of two different counterfactual
scenarios.

Site choices in recreational demand: a matter of utility maximization or regret minimization?

This paper compares the Random Regret Minimization and the Random Utility Maximization models for determining recreational choice. The Random Regret approach is based on the idea that, when choosing, individuals aim to minimize their regret – regret being defined as what one experiences when a non-chosen alternative in a choice set performs better than a chosen one in relation to one or more attributes. The Random Regret paradigm, recently developed in transport economics, presents a tractable, regret-based alternative to the dominant choice paradigm based on Random Utility. Using data from a travel cost study exploring factors that influence kayakers’ site-choice decisions in the Republic of Ireland, we estimate both the traditional Random Utility multinomial logit model (RU-MNL) and the Random Regret multinomial logit model (RR-MNL) to gain more insights into site choice decisions. We further explore whether choices are driven by a utility maximization or a regret minimization paradigm by running a binary logit model to examine the likelihood of the two decision choice paradigms using site visits and respondents characteristics as explanatory variables. In addition to being one of the first studies to apply the RR-MNL to an environmental good, this paper also represents the first application of the RR-MNL to compute the Logsum to test and strengthen conclusions on welfare impacts of potential alternative policy scenarios.

Random Regret Minimization: Exploration of a New Choice Model for Environmental and Resource Economics

This paper introduces the discrete choice model-paradigm of Random Regret Minimization (RRM) to the field of environmental and resource economics. The RRM-approach has been very recently developed in the context of travel demand modelling and presents a tractable, regret-based alternative to the dominant choice-modelling paradigm based on Random Utility Maximization-theory (RUM-theory). We highlight how RRM-based models provide closed form, logit-type formulations for choice probabilities that allow for capturing semi-compensatory behaviour and choice set-composition effects while being equally parsimonious as their utilitarian counterparts. Using data from a Stated Choice-experiment aimed at identifying valuations of characteristics of nature parks, we compare RRM-based models and RUM-based models in terms of parameter estimates, goodness of fit, elasticities and consequential policy implications.

The role of regret minimisation in lifestyle choices affecting the risk of coronary heart disease

This paper introduces the discrete choice model-paradigm of Random Regret Minimisation (RRM) to the field of health economics. The RRM is a regret-based model that explores a driver of choice different from the traditional utility-based Random Utility Maximisation (RUM). The RRM approach is based on the idea that, when choosing, individuals aim to minimise their regret–regret being defined as what one experiences when a non-chosen alternative in a choice set performs better than a chosen one in relation to one or more attributes. Analysing data from a discrete choice experiment on diet, physical activity and risk of a fatal heart attack in the next ten years administered to a sample of the Northern Ireland population, we find that the combined use of RUM and RRM models offer additional information, providing useful behavioural insights for better informed policy appraisal.

Stated choices and benefit estimates in the context of traffic calming schemes:Utility maximization, regret minimization, or both?

This paper proposes a discrete mixture model which assigns individuals, up to a probability, to either a class of random utility (RU) maximizers or a class of random regret (RR) minimizers, on the basis of their sequence of observed choices. Our proposed model advances the state of the art of RU-RR mixture models by (i) adding and simultaneously estimating a membership model which predicts the probability of belonging to a RU or RR class; (ii) adding a layer of random taste heterogeneity within each behavioural class; and (iii) deriving a welfare measure associated with the RU-RR mixture model and consistent with referendum-voting, which is the adequate mechanism of provision for such local public goods. The context of our empirical application is a stated choice experiment concerning traffic calming schemes. We find that the random parameter RU-RR mixture model not only outperforms its fixed coefficient counterpart in terms of fit-as expected-but also in terms of plausibility of membership determinants of behavioural class. In line with psychological theories of regret, we find that, compared to respondents who are familiar with the choice context (i.e. the traffic calming scheme), unfamiliar respondents are more likely to be regret minimizers than utility maximizers. © 2014 Elsevier Ltd.

Do Children Who Experience Regret Make Better Decisions? A Developmental Study of the Behavioral Consequences of Regret

Although regret is assumed to facilitate good decision making, there is little research directly addressing this assumption. Four experiments (N = 326) examined the relation between children's ability to experience regret and the quality of their subsequent decision making. In Experiment 1 regret and adaptive decision making showed the same developmental profile, with both first appearing at about 7 years. In Experiments 2a and 2b, children aged 6–7 who experienced regret decided adaptively more often than children who did not experience regret, and this held even when controlling for age and verbal ability. Experiment 3 ruled out a memory-based interpretation of these findings. These findings suggest that the experience of regret facilitates children's ability to learn rapidly from bad outcomes.