We study the effect of impairment on stochastic multi-armed bandits and develop new ways to mitigate it. Impairment effect is the phenomena where an agent only accrues reward for an action if they have played it at least a few times in the recent past. It is practically motivated by repetition and recency effects in domains such as advertising (here consumer behavior may require repeat actions by advertisers) and vocational training (here actions are complex skills that can only be mastered with repetition to get a payoff). Impairment can be naturally modelled as a temporal constraint on the strategy space, and we provide two novel algorithms that achieve sublinear regret, each working with different assumptions on the impairment effect. We introduce a new notion called bucketing in our algorithm design, and show how it can effectively address impairment as well as a broader class of temporal constraints. Our regret bounds explicitly capture the cost of impairment and show that it scales (sub-)linearly with the degree of impairment. Our work complements recent work on modeling delays and corruptions, and we provide experimental evidence supporting our claims.
@cite_18 consider the setting where the algorithm has access to previous plays of each arm and focus on warm-starting the exploration-exploitation process. This could be useful in our setting, where one can partition the initial set of arms into buckets such that impairment is mitigated, learn the local best arms in each bucket. Next, these best arms can be combined together (hierarchically agglomerate) and their historical plays can be used to warm-start. A rigorous analysis of this heuristic is a possible future work. In a similar vein of learning with previously collected observational data, @cite_20 focus on counterfactual risk minimization. While these works work with a one-time use of historical data to improve future payoffs, in our setting we work around the continual impact of historical actions on future payoffs. @cite_23 consider the problem of history-dependent arm selection against possibly adaptive adversaries, which is a much weaker setting compared to ours.
@cite_18 @cite_23 @cite_20
2187360726 2033530627 2950382198
In this paper we consider the stochastic multi-armed bandit problem. However, unlike in the conventional version of this problem, we do not assume that the algorithm starts from scratch. Many applications offer observations of (some of) the arms even before the algorithm starts. We propose three novel multi-armed bandit algorithms that can exploit this data. An upper bound on the regret is derived in each case. The results show that a logarithmic amount of historic data can reduce regret from logarithmic to constant. The eectiveness of the proposed algorithms are demonstrated on a large-scale malicious URL detection problem. Abstract The effects of emotional feelings during advertisement exposure and the effects of attitude toward the advertisement (Aad) are considered in an experiment which used both familiar and unfamiliar brands. The findings illustrate that brand familiarity moderates the relationships between Aad and brand attitude after advertisement exposure. In addition, the research provides evidence that the direct-affect-transfer hypothesis may be an adequate explanation for the effects of emotional feelings and Aad on brand attitude in some situations. We develop a learning principle and an efficient algorithm for batch learning from logged bandit feedback. This learning setting is ubiquitous in online systems (e.g., ad placement, web search, recommendation), where an algorithm makes a prediction (e.g., ad ranking) for a given input (e.g., query) and observes bandit feedback (e.g., user clicks on presented ads). We first address the counterfactual nature of the learning problem through propensity scoring. Next, we prove generalization error bounds that account for the variance of the propensity-weighted empirical risk estimator. These constructive bounds give rise to the Counterfactual Risk Minimization (CRM) principle. We show how CRM can be used to derive a new learning method -- called Policy Optimizer for Exponential Models (POEM) -- for learning stochastic linear rules for structured output prediction. We present a decomposition of the POEM objective that enables efficient stochastic gradient optimization. POEM is evaluated on several multi-label classification problems showing substantially improved robustness and generalization performance compared to the state-of-the-art.