Cascading Reinforcement Learning

• URL: http://arxiv.org/abs/2401.08961v4
• Date: Sun, 7 Apr 2024 05:29:24 GMT
• Title: Cascading Reinforcement Learning
• Authors: Yihan Du, R. Srikant, Wei Chen,
• Abstract summary: In cascading bandit model, at each timestep, an agent recommends an ordered subset of items from a pool of items, each associated with an unknown attraction probability. We propose a generalized cascading RL framework, which considers the impact of user states and state transition into decisions. In cascading RL, we need to select items not only with large attraction probabilities but also leading to good successor states. We develop two algorithms CascadingVI and CascadingBPI, which are both computationally-efficient and sample-efficient.
• Score: 21.267106043818792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cascading bandits have gained popularity in recent years due to their applicability to recommendation systems and online advertising. In the cascading bandit model, at each timestep, an agent recommends an ordered subset of items (called an item list) from a pool of items, each associated with an unknown attraction probability. Then, the user examines the list, and clicks the first attractive item (if any), and after that, the agent receives a reward. The goal of the agent is to maximize the expected cumulative reward. However, the prior literature on cascading bandits ignores the influences of user states (e.g., historical behaviors) on recommendations and the change of states as the session proceeds. Motivated by this fact, we propose a generalized cascading RL framework, which considers the impact of user states and state transition into decisions. In cascading RL, we need to select items not only with large attraction probabilities but also leading to good successor states. This imposes a huge computational challenge due to the combinatorial action space. To tackle this challenge, we delve into the properties of value functions, and design an oracle BestPerm to efficiently find the optimal item list. Equipped with BestPerm, we develop two algorithms CascadingVI and CascadingBPI, which are both computationally-efficient and sample-efficient, and provide near-optimal regret and sample complexity guarantees. Furthermore, we present experiments to show the improved computational and sample efficiencies of our algorithms compared to straightforward adaptations of existing RL algorithms in practice.

Related papers

• Efficient Recommendation with Millions of Items by Dynamic Pruning of Sub-Item Embeddings [63.117573355917465]
  We propose a dynamic pruning algorithm to efficiently find the top highest-scored items in a large item catalogue. Our RecJPQPrune algorithm is safe-up-to-rank K since it theoretically guarantees that no potentially high-scored item is excluded from the final top K recommendation list. Our experiments on two large datasets and three recommendation models demonstrate the efficiency achievable using RecJPQPrune.
  arXiv  Detail & Related papers  (2025-05-01T14:36:33Z)
• Review, Refine, Repeat: Understanding Iterative Decoding of AI Agents with Dynamic Evaluation and Selection [71.92083784393418]
  Inference-time methods such as Best-of-N (BON) sampling offer a simple yet effective alternative to improve performance. We propose Iterative Agent Decoding (IAD) which combines iterative refinement with dynamic candidate evaluation and selection guided by a verifier.
  arXiv  Detail & Related papers  (2025-04-02T17:40:47Z)
• OneRec: Unifying Retrieve and Rank with Generative Recommender and Iterative Preference Alignment [9.99840965933561]
  We propose OneRec, which replaces the cascaded learning framework with a unified generative model. OneRec includes: 1) an encoder-decoder structure, which encodes the user's historical behavior sequences and gradually decodes the videos that the user may be interested in.
  arXiv  Detail & Related papers  (2025-02-26T09:25:10Z)
• Improving Portfolio Optimization Results with Bandit Networks [0.0]
  We introduce and evaluate novel Bandit algorithms designed for non-stationary environments. First, we present the Adaptive Discounted Thompson Sampling (ADTS) algorithm. We then extend this approach to the Portfolio Optimization problem by introducing the Combinatorial Adaptive Discounted Thompson Sampling (CADTS) algorithm.
  arXiv  Detail & Related papers  (2024-10-05T16:17:31Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Optimizing Novelty of Top-k Recommendations using Large Language Models and Reinforcement Learning [16.287067991245962]
  In real-world systems, an important consideration for a new model is novelty of its top-k recommendations. We propose a reinforcement learning (RL) formulation where large language models provide feedback for the novel items. We evaluate the proposed algorithm on improving novelty for a query-ad recommendation task on a large-scale search engine.
  arXiv  Detail & Related papers  (2024-06-20T10:20:02Z)
• Model-based Causal Bayesian Optimization [74.78486244786083]
  We introduce the first algorithm for Causal Bayesian Optimization with Multiplicative Weights (CBO-MW) We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. Our experiments include a realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system.
  arXiv  Detail & Related papers  (2023-07-31T13:02:36Z)
• Generative Slate Recommendation with Reinforcement Learning [49.75985313698214]
  reinforcement learning algorithms can be used to optimize user engagement in recommender systems. However, RL approaches are intractable in the slate recommendation scenario. In that setting, an action corresponds to a slate that may contain any combination of items. In this work we propose to encode slates in a continuous, low-dimensional latent space learned by a variational auto-encoder. We are able to (i) relax assumptions required by previous work, and (ii) improve the quality of the action selection by modeling full slates.
  arXiv  Detail & Related papers  (2023-01-20T15:28:09Z)
• Fast online ranking with fairness of exposure [29.134493256287072]
  We show that our algorithm is computationally fast, generating rankings on-the-fly with computation cost dominated by the sort operation, memory efficient, and has strong theoretical guarantees. Compared to baseline policies that only maximize user-side performance, our algorithm allows to incorporate complex fairness of exposure criteria in the recommendations with negligible computational overhead.
  arXiv  Detail & Related papers  (2022-09-13T12:35:36Z)
• Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
  In some applications such as recommendation systems, the statistician is primarily interested in recovering the set of the top ranked items from a large pool of items. We propose the choice-based Borda count algorithm as a fast and accurate ranking algorithm for top $K$-recovery. We show that the choice-based Borda count algorithm has optimal sample complexity for top-$K$ recovery under a broad class of random utility models.
  arXiv  Detail & Related papers  (2022-06-23T22:05:08Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• CRACT: Cascaded Regression-Align-Classification for Robust Visual Tracking [97.84109669027225]
  We introduce an improved proposal refinement module, Cascaded Regression-Align- Classification (CRAC) CRAC yields new state-of-the-art performances on many benchmarks. In experiments on seven benchmarks including OTB-2015, UAV123, NfS, VOT-2018, TrackingNet, GOT-10k and LaSOT, our CRACT exhibits very promising results in comparison with state-of-the-art competitors.
  arXiv  Detail & Related papers  (2020-11-25T02:18:33Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  We introduce Coop-FTPL, a cooperative version of the well-known Follow The Perturbed Leader algorithm. We show that the expected regret of our algorithm after T time steps is of order QT log(k)(k$alpha$ 1 /Q + m), where Q is the total activation probability mass.
  arXiv  Detail & Related papers  (2020-10-05T07:08:26Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.