MultiScale Contextual Bandits for Long Term Objectives

We thank the reviewer for their time and effort for this valuable service.

We are glad that all four reviewers unanimously acknowledge the novelty of the method with high scores along the axis of Originality.

The concerns raised are primarily clarifications. We address each of them below.

How does errors/noise in short term feedback affect macro policy

Our experiment in Figure 13 of Appendix looks at how noise in micro policy affects macro policy learning. We evaluate for varying levels of noise by perturbing the ranking scores. While the noise at micro level does affect long term optimization, we find that empirically macro learning is still robust to fairly large values of noise at micro level and maintains its advantage over the baselines (including the baseline of only learning from short term "short term opt"). Please also see the response to reviewer mEmM under “how much the prior advantage contributes to the macro-level improvement”.

Computational cost of hierarchical learning

• In order to compare the computation cost we analyze the samples required for directly optimizing long term feedback versus our approach of hierarchical learning in section 3. While MSPL learns a policy at each level, eq 4 shows that hierarchical learning would be beneficial to learning a single- level policy from an uniformed prior depending on the misalignment between different timescale feedback. As reviewer z6c1 noted “By re-using micro-level knowledge as a Bayesian prior, MSBL needs dramatically fewer long-term samples to reach reliable macro policies—crucial when retention or renewal labels are rare.”
• Aditionally, as noted in lines 234-236, the macro action space (decoding strategies, reward weights etc.) is much smaller than that of the micro level (rankings, token action space) so that the macro policies are progressively smaller in size.

We thank the reviewer for their time and effort for this valuable service.

We are glad that all four reviewers unanimously acknowledge the novelty of the method with high scores along the axis of Originality and the reviewer noted “The proposed hierarchical separation is quite general and powerful in capturing a wide range of situations.” Reviewer mEmM also noted “The hierarchical treatment of feedback across multiple timescales is novel, providing a compelling approach to reconciling short-term actions with long-term outcomes.”

The concerns raised are primarily clarifications. We address each of them below.

empirical evaluation and tasks

We are glad that the reviewer noted “The empirical validation is extensive. The paper evaluates three distinct and relevant tasks: a multi-turn conversation task, a simulated conversational recommender system, and a recommender system built on a video streaming benchmark dataset.”

• Regarding the synethtic nature of the tasks studied, we emphasize these are semi-synthetic experiments and the best available option in the absence of open source real world datasets for this problem. Below we detail how each of the tasks are formed from either real world data where possible (level 1) or simulated according to existing literature (for medium and long term feedback).

  1. Our first experiment on multi-turn conversations is based on Anthropic’s helpful-harmless dataset [4] and 7b model similar to those in [1]. <!-- The difference from [1] is that [1] does not address or take into account the long term feedback. --> To obtain long term feedback on this task, we set up a user-agent multi turn conversation where the user is instantiated with a LLama-70B. This multi-turn setup is used in [3]. We let the conversation continue for up to 5-turns and obtain the long term feedback from LLama-70B with LLM as judge [6].

  2. The second task, where we built a simulator to demonstrate three levels for a conversational recommender system, is again based on the 7b model as in [1]. We model medium and long term feedback, similar to the long term constraints formulation in [2], where the long term constraints are only observed after T steps and the constraint satisfaction depends on all the actions taken during that time period. In [2], the authors used Kauirand dataset [5] and formed long term constraints as a function of exposure targets. In our work, we similarly form long term feedback based on user preferences. The difference from [2] is that while [2] assumes the long term intervention as given, we learn it with L2 policy.

  3. The third task based on a real world video streaming app uses the dataset of engagements collected from real user interactions [5]. This experiment uses real user features and their interactions with a catalog of ~5K items for level 1. We formulate the long term feedback similar to that in [2].

     [1] Rewards-in-Context: Multi-objective Alignment of Foundation Models with Dynamic Preference Adjustment (Yang et al'24)

     [2] Ranking with Long term constraints (Brantley et al'24)

     [3] Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHF (Gao et al'25)

     [4] Anthropic’s helpful-harmless dataset

     [5] KuaiRec dataset for recommender systems (Gao et al'22)

     [6] LLM as judge

• While we agree that deployment in a production system would be an interesting next step, our key contribution is the conceptualization of the new multi-scale formulation, which the reviewers acknowledge as interesting and important - and for which we provide both a PAC-Bayesian motivation and extensive empirical evaluation of semi-synthetic data. Whether this approach performs well on a particular industrial application cannot be a requirement for publication, and most NeurIPS papers do not provide such experiments.

strongly tuned baselines in real world systems

• Heavily engineered production systems over many years can get excellent performance through manual tuning and complex sets of business rules for effective long term behavior. We kindly emphasize that is not the point of our research. The goal of our research is to provide a principled and general method for learning systems with effective long-term behavior for a variety of domains. To validate this, we provide both a PAC-Bayesian motivation and extensive empirical evaluation on semi-synthetic baselines.

• In particular, we formed the baselines similar to other accepted papers in the community [1,2]. In [1] the authors provide baselines as the base LLM policy with and without their proposed module of predicting personalized temperature. [1] does not address or model the problem of long term objectives. In [2], the baselines consist of myopic controllers (short term optimizing baseline) and other proposed controllers that optimize for different formulations of long term constraints similar to our baselines for different types of macro interventions.

  [1] To Cool or not to Cool? Temperature Network Meets Large Foundation Models via DRO (Qiu et al'24)

  [2] Ranking with Long term constraints (Brantley et al'24)

Conceptual vs technical novelty

We thank the reviewer for acknowledging the conceptual novelty of our proposed framework that is general and powerful for optimizing long term outcomes. The reviewer also clearly described our contributions of proposing two ways of building a family of policies at micro level (policy and feedback modifications).

As we noted in the conclusion, there are many other ways of instantiating the general MSPL framework with other algorithms (and potentially new estimators) as an interesting direction for future work.

Factorization of policies

Thanks for raising this important point and letting us clarify. In section 4, we introduce multiscale policies by factoring a monolithic policy space $\Pi$ as $\Pi^{L1} \cdot \Pi^{L2}$. By this, we meant that we can decompose the policy space $\Pi$ into decoupled and independent learning at each level.

As shown in Figure 2(b), learning a family of policy from the entire policy space at Level 1 ($\Pi^{L1}$) consists of finding a set $\hat{\Pi}^{L1}= \{\hat{\pi}^{L1}_{a^{L2}}; a^{L2} \in \mathcal{A}^{L2}\}$. The entire policy space $\Pi^{L1}$ can be viewed as consisting of different sets of $\hat{\Pi}^{L1}$. At level 2, we find a policy $\pi^{L2} \in \Pi^{L2}$ as shown in Figure 2 ( c ). The factorization refers to learning a family of policy at L1 decoupled from learning $\pi^{L2}$ at level 2.

During inference as shown in Figure 2(a) the selection is conditional, where $a^{L2}$ is first selected from the learned $\pi^{L2}(a^{L2}|x^{L2})$ and the lower level action is selected according to $\pi_{a^{L2}}^{L1} (a^{L1}|x^{L2})$
This does indeed make the overall action selection a conditional product of policies $\pi^{L2}$ and $\pi^{L1}_{a^{L2}}$.

We will add this clarification in section 4 of the main text.

Action subscripts in Figure 3

The action subscripts in Figure 3 stand for static L2 interventions, where $a^{L2} \in$ [0.8(harml-), 0.2(helpf-)], [0.2(harml-), 0.8(helpf-)]. $a^{L2}_1$ referes to the same L1 policy as other baselines but using the fixed L2 intervention of preference weights in [0.8(harml-), 0.2(helpf-)] , while $a^{L2}_2$ refers to using the fixed L2 intervention of preference weights in [0.2(harml-), 0.8(helpf-)]. We describe this in Appendix F.2 but will clarify it in the main text.

We thank the reviewer for their time and effort for this valuable service.

We are glad that all four reviewers unanimously acknowledge the novelty of the method with high scores along the axis of Originality. We are glad that the reviewer found our proposed algorithm "easy to plug into existing ranking, LLM decoding or recommendation stacks" and noted that "Across chat, simulated and real-world recommender tasks, MSBL consistently lifts long-horizon objectives while keeping click/engagement drops small and showing resilience to noisy features or larger action spaces."

The concerns raised are primarily misunderstandings. We clarify each of them and address them below.

Empirical support for core motivation

• In recommender systems, over-optimization of clicks leading to lower user retention [1, 2], challenges in aligning short, medium and long session goals [3] and challenges with competing time horizon objectives [4] have been extensively reported. For instance, [4] describes time horizon objectives in Figure 1 (short term as click through rate, and long term as customer satisfaction) and states that “long-term and short-term objectives may be competing”. They discuss existing recommendation paradigms and conclude that “Such strategies that are successful in the short term may however be non-optimal or even detrimental in the long run.”

• This misalignment between micro and macro objectives has been shown to be substantial [2,8]. Specifcially, Figure 2 of [2] shows the dcg metric for the micro/short term utility of micro actions (ranking) and the macro violation for the long term constraint violation. Similarly, [8] shows the tradeoff between utility and amortized exposure (collected over a time horizon T) as the macro goal. These works assume that the macro intervention is given while our work learns it via the macro policy.

• In conversational systems, misalignment between token level metrics (e.g., perplexity) and multiple responses/document level metric (e.g., diversity in a paragraph) has been studied both qantitatively and qualitatively in [5, 6, 7].

As a result, there is overwhelming evidence that short-term objectives can be substantially misaligned with long-term objectives across a wide range of applications.

Please also note that most reviewers found the problem important and timely. Reviewer mEmM noted “The problem of optimizing long-term objectives in AI systems is both timely and important, especially given the prevalence of short-term optimization in practice.”, reviewer PY8n noted "The paper addresses a critical challenge in interactive AI systems, where short-term feedback is abundant, but optimizing solely for it often harms long-term objectives." and reviewer enko also noted “The problem being addressed is ubiquitous in practical applications, and so quite important.”

short-term metrics often correlate well with long-term outcomes, which the paper itself implicitly assumes when using L1 feedback to construct priors for L2 learning.

This is an important and subtle point. While short term metrics provide an important signal for long term outcomes, their unmitigated optimization is not necessarily aligned with long term goals (as we provided evidence above). In our work, we provide a principled way of modifying the policy or the feedback so that while there may be a sacrifice in the short term metrics (e.g clicks, perplexity of a sentence) but the modified policy is more effective at optimizing upper level reward (e.g., fewer clicks by more aggressively pruning suspected click bait can lead to better weekly returns or transforming the short term rewards to steer for long term goals). See lines 189-192 and lines 206-208 in the main text.

when/why our method provides advantage over existing flat learning methods

• Existing flat learning methods such as [2,9] consider optimizing for L1 actions only (rankings). They do not learn L2 interventions such as reward weights [10], ads [11], ad pacing [12], message notifications, decoding strategies [5] etc that are available in the system and can directly steer the system towards long term objectives.
• The literature on delayed rewards such as [9] and the related works that the reviewer pointed out model the delayed reward of a micro level action. Crucially, they do not address the situation where the delayed long term reward cannot be attributed to a single micro level action, but is the result of multiple actions. For instance, diversity among T generated responses by an LLM policy depends on all the responses generated within the T horizon; similarly, a specific exposure target as a long term goal depends on rankings over the entire T horizon [2].
• unlike the flat learning methods [2,9], our framework extends to more than two timescales of competing objectives. These flat learning methods can in fact be plugged into a single level (usually the lowest level) in the MSPL framework.

Focus on off-policy

In this work we focus on off policy learning (OPL) using naturally collected logged bandit data.

• OPL is of great practical relevance, as it enables improving the system without the risky, slow, and potentially unethical use of online exploration [13,14,15].
• Importantly, access to logged bandit data is not considered an assumption but is naturally collected in most real setting [13,14,15] .
• While one could swap out the off-policy method with an on-policy method (e.g., REINFORCE policy gradient) and develop MSPL with online estimators, it is out of the scope of the current work. Instead we discuss the deployment of MSBL policies and their adaptation at inference time (as new data arrives).

Adapting to dynamic environments

Please refer to the response to reviewer mEmM on “Updating MSBL policies as new data arrives”. We provide clarification on how the different levels can be updated asynchronously (offline) and provide empirical results.

Exploration-exploitation tradeoffs in online systems

Addressing exploration-exploitation tradeoffs is important but orthogonal to the focus of our work. We described in the response under “Updating MSBL policies as new data arrives” how policies at different levels can be updated asynchronously. With that discussion as the context, one can also update MSBL policies incorporating exploration from existing UCB or thompson sampling works to balance this tradeoff. To reiterate, centering our work on off-policy learning (OPL) has its own merits and practical relevance [15].

Related works

We will move the discussion on related works in this response and that in the appendix to the main text to incorporate these clarifications.

[1] Focusing on the Long-term: It's Good for Users and Business (Hohnhold et al'15)

[2] Ranking with Long term constraints (Brantley et al'24)

[3] A Survey on Session-based Recommender Systems (Wang et al'21)

[4] A survey on multi-objective recommender systems (Jannach et al'23)

[5] Adaptive Decoding via Latent Preference Optimization (Dhiliawala et al'24)

[6] Perplexity by PLM Is Unreliable for Evaluating Text Quality (Wang et al'23)

[7] Escaping the sentence-level paradigm in machine translation (Post et al'24)

[8] Controlling Fairness and Bias in Dynamic Learning-to-Rank (Morik et al'20)

[9] Impatient Bandits (Zhang et al'24)

[10] From Optimizing Engagement to Measuring Value (Milli et al'21)

[11] Control-based Bidding for Mobile Livestreaming Ads with Exposure Guarantee (Zhang et al'22)

[12] Smart Pacing for Effective Online Ad Campaign Optimization (Xu et al'15)

[13] Counterfactual Risk Minimization: Learning from Logged Bandit Feedback (Swaminathan et al'15)

[14] Off-Policy Evaluation for Large Action Spaces via Policy Convolution (Sachdeva et al'23)

[15] Off-Policy Evaluation and Learning in Recommender Systems (Recsys 2021 Tutorial)

We thank the reviewer for their time and effort for this valuable service.

We are glad that all four reviewers unanimously acknowledge the novelty of the method with high scores along the axis of Originality. To quote, the reviewer noted “The hierarchical treatment of feedback across multiple timescales is novel, providing a compelling approach to reconciling short-term actions with long-term outcomes.” Reviewer enko also noted “The proposed hierarchical separation is quite general and powerful in capturing a wide range of situations.”

The concerns raised are primarily clarifications. We address each of them below.

experiment setup on synthetic simulators

The reviewers largely agree that the paper tackles a significant, timely and an important problem. To progress research in this direction, we used real world datasets/ setup in existing papers [1,4,5] for level 1 and simulate medium and long term feedback (following previous works [2,3,6]). For our simulator with three levels, we describe the design and modules in Figure 6 of Appendix and open source it as part of the paper.<!-- These are semi-synthetic experiments and the best available option in the absence of open source real world datasets for this problem. --> Please also refer to our response to reviewer enko under "empirical evaluation".

[1] Rewards-in-Context: Multi-objective Alignment of Foundation Models with Dynamic Preference Adjustment (Yang et al'24)

[2] Ranking with Long term constraints (Brantley et al'24)

[3] Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHF (Gao et al'25)

[4] Anthropic’s helpful-harmless dataset

[5] KuaiRec dataset for recommender systems (Gao et al'22)

[6] LLM as judge

PAC Bayesian theoretical insights vs guarantees

Thanks for acknowledging the valuable theoretical insight of the PAC Bayes motivation. While we provide an upper bound for improvement in required training samples in eq (4), providing a practically meaningful formal guarantee is challenging given the complexity of the models involved. We see the value of the PAC Bayes analysis in validating the principle behind our model, not quantifying the outcome.

Updating MSBL policies as new data arrives

This is a great question. The macro policy is adaptable and can be updated when new data arrives. An on policy estimator (e.g., REINFORCE policy gradient) could be used but our work is centered on off-policy learning (OPL) setting. Below we describe the scenarios and provide empirical results with and without updating L2 policy (offline) as new macro data arrives.

MSPL decouples the micro and macro policy learning so that they can be updated asynchronously.

• If new macro level data arrives (e.g changing user preferences), the family of policies at the micro level do not need to be updated. We only need to update the macro policy that selects the optimal macro intervention according to the new macro data. This is advantageous as compared to methods that reviewer z6c1 referred to as incorporating L2 learning as part of L1 learning policy. For such methods, one would need to update a single monolithic deployed policy if any new data arrives. MSPL's modular design allows decoupled learning between levels.

  To demonstrate this empirically, we conduct an experiment for the last setup - two levels of large scale recommendation system with the MSBL policies deployed. We simulate a scenario such that the underlying user preferences change after deployment. In the below results the first row "w. new macro data" shows both long and short term reward without updating the L2 policy and the second row shows the expected rewards after L2 policy is updated according to the new macro level data. Across different number of user groups we can see that while the micro level (clicks) remains mostly unchanged, only updating macro policy results in lifting the long term.

  2 Groups	Long term (Return Rate) $\uparrow$	Short term (Clicks) $\uparrow$
  w. new macro data	0.64$\pm$ 0.01	239.62 $\pm$ 0.68
  w. L2 policy updated	0.65 $\pm$ 0.01	239.70 $\pm$ 0.62
  % Improv. w. updating L2	$\mathbf{1.37}$ %	$0.03$ %

  3 Groups	Long term (Return Rate) $\uparrow$	Short term (Clicks) $\uparrow$
  w. new macro data	0.48 $\pm$ 0.12	240.50 $\pm$ 0.76
  w. L2 policy updated	0.54 $\pm$ 0.07	240.13 $\pm$ 0.41
  % Improv. w. updating L2	$\mathbf{14.46}$ %	$-0.15$ %

  4 Groups	Long term (Return Rate) $\uparrow$	Short term (Clicks) $\uparrow$
  w. new macro data	0.42 $\pm$ 0.08	240.48 $\pm$ 0.78
  w. L2 policy updated	0.45 $\pm$ 0.06	240.42 $\pm$ 0.83
  % Improv. w. updating L2	$\mathbf{8.14}$ %	$-0.02$%

• On the other hand, new micro-level data (for instance with addition of items in catalog, updates required in the base LLM policy etc.) would require updating both micro and macro policy.

• Finally, this framework elegantly scales to more than two levels when new data arrives. For instance, for three levels, if new data arrived for L2, only L2 and L3 policy need to be updated. The L1 policy would remain unchanged. Below, we show with an experiment on the second setup - a three level simulator that new L2,L3 data only affects the medium and long term and the L1 policy does not need to be updated.

  2 Groups	Long term	Medium term	Short term
  w. new L2, L3 data	0.88	0.85	0.52
  w. L2, L3 policy updated	0.98	0.90	0.52
  % Improv. w. updating L2 & L3	$\mathbf{11.59 }$ %	$\mathbf{5.76}$ %	$0.61$%

Extending to reinforcement learning beyond bandits

This is another great point. We note in limitations, line 354 that “extension to stateful policies would be an interesting future work”. We conjecture such an extension to be straightforward especially if dependencies at the lower level stay within the timestep of the next higher level. For example, in experiment 2 (conversational recommender simulator) for the lowest level, we already append the response of the L1 LLM policy at each timestep to the next context, so that the current context depends on the action taken in previous timestep. However, a more general and fully principled extension of MSPL to MDP policies requires careful consideration and challenges related to learning MDP policies with scarce data.

Regarding

how much the prior advantage contributes to the macro-level improvement,

To evaluate the prior advantage from micro level learning, we conduct an experiment where we inject noise into the micro learning process and see how it affects macro level rewards for the last setup - two levels of large scale recommendation system. A noise of 0.4 refers to 40% randomness in micro action selection. Below , we can see that the advantage of micro level when learned (w. 0.0 noise) is significant compared to a random micro policy (w. 1.0 noise)