Daniel Russo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Daniel Russo has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
Benjamin Van Roy
Department of Electrical Engineering and Department of Management Science and Engineering, Stanford University, Stanford, California 94305
2 shared publications- Benjamin Van Roy
Stanford University Stanford CA
2 shared publications - Abbas Kazerouni
Department of Electrical Engineering Stanford University 94305 Stanford CA
1 shared publication - Anthony Kim
Amazon, New York, New York 10001
1 shared publication - Antonina Danylenko
Spotify, Sweden
1 shared publication - Babak Loni
Meta, Netherlands
1 shared publication
Latest Publications
- Open Access
- 8 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1210-1212
SURE 2024: Workshop on Strategic and Utility-aware REcommendation
- 8 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1210-1212
Open AccessSURE 2024: Workshop on Strategic and Utility-aware REcommendation
- Top Cited Papers
- 1 September 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72 (5) , 1906-1927
Global Optimality Guarantees for Policy Gradient Methods
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.
- 1 September 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72 (5) , 1906-1927
Top Cited PapersGlobal Optimality Guarantees for Policy Gradient Methods
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.
- 15 July 2024
- Published by Springer Nature in Behavior Analysis in Practice
- Vol. 17 (4) , 977-995
Development of the Values-Centered Assessment Tool (VCAT) to Inform Culturally Responsive Behavioral Services
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.
- 15 July 2024
- Published by Springer Nature in Behavior Analysis in Practice
- Vol. 17 (4) , 977-995
Development of the Values-Centered Assessment Tool (VCAT) to Inform Culturally Responsive Behavioral Services
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.
- 1 November 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 69 (11) , 6898-6911
Approximation Benefits of Policy Gradient Methods with Aggregated States
- 1 November 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 69 (11) , 6898-6911
Approximation Benefits of Policy Gradient Methods with Aggregated States
- Open Access
Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation
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 AccessAdaptive Experimentation in the Presence of Exogenous Nonstationary Variation
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
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1687-1697
Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay
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.
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1687-1697
Open AccessImpatient Bandits: Optimizing Recommendations for the Long-Term Without Delay
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.
- 1 November 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (4) , 2815-2839
Satisficing in Time-Sensitive Bandit Learning
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.
- 1 November 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (4) , 2815-2839
Satisficing in Time-Sensitive Bandit Learning
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.
- 1 November 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (6) , 1767-1783
On the Futility of Dynamics in Robust Mechanism Design
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.
- 1 November 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (6) , 1767-1783
On the Futility of Dynamics in Robust Mechanism Design
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.
- 1 May 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (3) , 950-973
A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation
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.
- 1 May 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (3) , 950-973
A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation
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.
- 1 January 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (1) , 273-278
Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
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.
- 1 January 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (1) , 273-278
Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
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.