DRDaniel Russo

Daniel Russo

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Daniel Russo has a total of 23 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    SURE 2024: Workshop on Strategic and Utility-aware REcommendation

    by Himan Abdollahpouri, Tonia Danylenko, Masoud Mansoury, Babak Loni, Daniel Russo, Mihajlo Grbovic

  • Top Cited Papers

    Global Optimality Guarantees for Policy Gradient Methods

    by Jalaj Bhandari, Daniel Russo

    Policy gradient methods, which have powered a lot of recent success in reinforcement learning, search for an optimal policy in a parameterized policy class by performing stochastic gradient descent on the cumulative expected cost-to-go under some initial state distribution. Although widely used, these methods lack theoretical guarantees as the optimization objective is typically nonconvex even for simple control problems, and hence are understood to only converge to a stationary point. In “Global Optimality Guarantees for Policy Gradient Methods,” J. Bhandari and D. Russo identify structural properties of the underlying MDP that guarantee that despite nonconvexity, the optimization objective has no suboptimal stationary points, ensuring asymptotic convergence of policy gradient methods to globally optimal policies. Under stronger conditions, authors show the policy gradient objective to satisfy a Polyak-lojasiewicz (gradient dominance) condition that yields fast convergence rates. In addition, when some of the said conditions are relaxed, authors provide bounds on the suboptimality gap of any stationary point. The results rely on a key connection with policy iteration, a classic dynamic programming algorithm which solves a single period optimization problem at every step. The authors show how structure in the single period optimization problems solved by policy iteration translate into nice properties of the multiperiod policy gradient objective, making it amenable for first-order methods to find globally optimal solutions. The authors also instantiate their framework for several classical control problems including tabular and linear MDPs, linear quadratic control, optimal stopping, and finite-horizon inventor control problems.


  • Development of the Values-Centered Assessment Tool (VCAT) to Inform Culturally Responsive Behavioral Services

    by Daniel Kwak, Kwang-Sun C. Blair, Danielle Russo

    Taking an individualized approach to cultural responsiveness is essential when collaborating with families to deliver behavior-analytic services. One way behavior analysts can start this process is by asking caregivers and other relevant individuals informed and targeted questions that would allow behavior analysts to make cultural adaptations to services that are provided. However, there is a lack of well-developed resources that are specific to behavior-analytic practice and designed to assist behavior analysts in facilitating conversations regarding values and cultures of clients and their families. Therefore, the purpose of this study was to develop the Values-Centered Assessment Tool (VCAT) to offer a way for behavior analysts to assess a wide range of potential adaptations that may be incorporated into the process of behavioral assessment, training, and intervention. To develop the tool, rigorous standards were adopted, including an extensive review of the literature, in-depth interviews with service providers (behavior analysts), and evaluation by an expert panel. The final version of the VCAT included questions about stakeholders, cultural practices, communication, client–professional relationship, accessibility, and parenting/behavior management. Results showed that the VCAT was representative of the content being assessed (S-CVI = .89) and demonstrated high content validity indexes for relevance (I-CVI = .99) and clarity (I-CVI = .98) of items. The VCAT was determined to be a content-valid tool that can be used to design individualized behavioral services with consideration of values and cultures of families who are from diverse cultural backgrounds.


  • Open Access

    Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation

    by Chao Qin, Daniel Russo

    We investigate experiments that are designed to select a treatment arm for population deployment. Multi-armed bandit algorithms can enhance efficiency by dynamically allocating measurement effort towards higher performing arms based on observed feedback. However, such dynamics can result in brittle behavior in the face of nonstationary exogenous factors influencing arms' performance during the experiment. To counter this, we propose deconfounded Thompson sampling (DTS), a more robust variant of the prominent Thompson sampling algorithm. As observations accumulate, DTS projects the population-level performance of an arm while controlling for the context within which observed treatment decisions were made. Contexts here might capture a comprehensible source of variation, such as the country of a treated individual, or simply record the time of treatment. We provide bounds on both within-experiment and post-experiment regret of DTS, illustrating its resilience to exogenous variation and the delicate balance it strikes between exploration and exploitation. Our proofs leverage inverse propensity weights to analyze the evolution of the posterior distribution, a departure from established methods in the literature. Hinting that new understanding is indeed necessary, we show that a deconfounded variant of the popular upper confidence bound algorithm can fail completely.

  • Open Access

    Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay

    by Thomas M. McDonald, Lucas Maystre, Mounia Lalmas, Daniel Russo, Kamil Ciosek

    Recommender systems are a ubiquitous feature of online platforms. Increasingly, they are explicitly tasked with increasing users' long-term satisfaction. In this context, we study a content exploration task, which we formalize as a multi-armed bandit problem with delayed rewards. We observe that there is an apparent trade-off in choosing the learning signal: Waiting for the full reward to become available might take several weeks, hurting the rate at which learning happens, whereas measuring short-term proxy rewards reflects the actual long-term goal only imperfectly. We address this challenge in two steps. First, we develop a predictive model of delayed rewards that incorporates all information obtained to date. Full observations as well as partial (short or medium-term) outcomes are combined through a Bayesian filter to obtain a probabilistic belief. Second, we devise a bandit algorithm that takes advantage of this new predictive model. The algorithm quickly learns to identify content aligned with long-term success by carefully balancing exploration and exploitation. We apply our approach to a podcast recommendation problem, where we seek to identify shows that users engage with repeatedly over two months. We empirically validate that our approach results in substantially better performance compared to approaches that either optimize for short-term proxies, or wait for the long-term outcome to be fully realized.


  • Satisficing in Time-Sensitive Bandit Learning

    by Daniel Russo, Benjamin Van Roy

    Much of the recent literature on bandit learning focuses on algorithms that aim to converge on an optimal action. One shortcoming is that this orientation does not account for time sensitivity, which can play a crucial role when learning an optimal action requires much more information than near-optimal ones. Indeed, popular approaches, such as upper-confidence-bound methods and Thompson sampling, can fare poorly in such situations. We consider instead learning a satisficing action, which is near-optimal while requiring less information, and propose satisficing Thompson sampling, an algorithm that serves this purpose. We establish a general bound on expected discounted regret and study the application of satisficing Thompson sampling to linear and infinite-armed bandits, demonstrating arbitrarily large benefits over Thompson sampling. We also discuss the relation between the notion of satisficing and the theory of rate distortion, which offers guidance on the selection of satisficing actions.


  • On the Futility of Dynamics in Robust Mechanism Design

    by Santiago R. Balseiro, Anthony Kim, Daniel Russo

    We consider a principal who repeatedly interacts with a strategic agent holding private information. In each round, the agent observes an idiosyncratic shock drawn independently and identically from a distribution known to the agent but not to the principal. The utilities of the principal and the agent are determined by the values of the shock and outcomes that are chosen by the principal based on reports made by the agent. When the principal commits to a dynamic mechanism, the agent best-responds to maximize his aggregate utility over the whole time horizon. The principal’s goal is to design a dynamic mechanism to minimize his worst-case regret, that is, the largest difference possible between the aggregate utility he could obtain if he knew the agent’s distribution and the actual aggregate utility he obtains. We identify a broad class of games in which the principal’s optimal mechanism is static without any meaningful dynamics. The optimal dynamic mechanism, if it exists, simply repeats an optimal mechanism for a single-round problem in each round. The minimax regret is the number of rounds times the minimax regret in the single-round problem. The class of games includes repeated selling of identical copies of a single good or multiple goods, repeated principal-agent relationships with hidden information, and repeated allocation of a resource without money. Outside this class of games, we construct examples in which a dynamic mechanism provably outperforms any static mechanism.


  • A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation

    by Jalaj Bhandari, Daniel Russo, Raghav Singal

    Temporal difference learning (TD) is a simple iterative algorithm widely used for policy evaluation in Markov reward processes. Bhandari et al. prove finite time convergence rates for TD learning with linear function approximation. The analysis follows using a key insight that establishes rigorous connections between TD updates and those of online gradient descent. In a model where observations are corrupted by i.i.d. noise, convergence results for TD follow by essentially mirroring the analysis for online gradient descent. Using an information-theoretic technique, the authors also provide results for the case when TD is applied to a single Markovian data stream where the algorithm’s updates can be severely biased. Their analysis seamlessly extends to the study of TD learning with eligibility traces and Q-learning for high-dimensional optimal stopping problems.


  • Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents

    by Daniel Russo

    This note gives a short, self-contained proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multiarmed bandit problem with discount factor [ ]. The Gittins index of an arm is shown to equal the [ ]-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as [ ]. In this sense, for sufficiently patient agents, a Gittins index measures the highest plausible mean-reward of an arm in a manner equivalent to an upper confidence bound.