A Reduction-based Framework for Sequential Decision Making with Delayed Feedback

Summary

The paper studies the problem of sequential decision-making problems with delayed feedback. The authors propose a reduction from standard sequential decision-making algorithms to the following problem providing regret guarantees in many settings: linear bandits, tabular RL, linear and general function approximations RL, tabular and linear zero-sum Markov Games, tabular general-sum Markov Games.

Strengths

- The authors improve previous results in the delayed feedback setting for multi-armed bandit, linear bandit, tabular MDP, tabular multi-player general sum MGs. - The authors provide the first regret guarantees (in the delayed feedback setting) for linear MDPs, general-function approximation MDPs, and tabular and linear two-player zero-sum MGs. - The strategy is simple: - single-agent: apply multi-batched algorithm for RL to the delayed feedback setting running some extra steps depending on the feedback delay $\tau_k$. - zero-sum tabular and general-sum tabular: using the doubling trick to update the policy. - zero-sum linear: update the policy when there exists $h \in [H]$ such that $\text{det}(\Lambda^k_h) > \eta \cdot \text{det}(\Lambda_h)$.

Weaknesses

### Presentation The presentation of the paper can be improved. The paper proposes a general strategy to convert multi-batch algorithms to the delayed feedback setting, changing (if I understood correctly) when the policy is updated. This is a simple and elegant transformation and it is not very clear from the presentation where the authors divide the transformations into three sections without providing this connection between them. I suggest providing an algorithm for the general setting which changes the update depending on the setting. Moreover, there are some minor issues in the way the algorithms are presented: - provide the input parameters in a clear way (e.g. algorithm 1 what is $l_m$?, algorithm 2 how can we compute $\tau_t$ since it is a random variable, algorithm 4 what is i?) - provide output to the algorithms. ### Novelty The simplicity of the strategy can be seen as a lack of novelty (due also to the previous point (see Presentation)). I suggest making more clear the challenges.

Questions

See weaknesses. Some minor questions: - In algorithm 2, do we know $\tau_t$ or are we waiting until we do not receive the feedback, and then we can evaluate $\tau_t$? - From a technical point of view what are the main challenges in converting regret bounds from the "classic" setting to the delayed feedback one?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The paper is mainly theoretical and the algorithms presented are not easily usable in practice.

Summary

This submission studies the problem of learning from delayed feedback in various online learning settings including multi-armed bandits, linear bandits, linear MDPs, RL with function approximation, and various markov game settings (among others). Delays are assumed to be i.i.d. random variables. Additionally, they are sometimes assumed to be subexponential random variables. The authors main result is a framework for sequential decision making with delayed feedback. Their framework makes use of "multi-batched" algorithms, which, as the name suggests, runs in batches. In each batch, a multi-batched algorithm outputs a sequence of policies to be used one-after-one (which are trained using data from previous batches), as well as a stopping criterion which decides when to stop the current batch. After a batch is run, the new data is incorporated with the existing data and is used to produce a new sequence of policies and stopping rule for the next round. At a high level, the framework converts a multi-batched algorithm for the setting of interest (e.g. linear bandits) to one which can handle delayed feedback. The key idea is to run the policy given by the multi-batched algorithm for some extra time-steps in order to satisfy the stopping criteria. The authors are then able to bound the additional regret due to the delayed feedback by bounding the number of additional steps needed to satisfy the stopping criteria. By instantiating their framework in the various settings listed above, they can obtain provable guarantees on the learner's regret. The rates obtained improve upon existing results in some settings (e.g. linear bandits and tabular MDPs), are slightly worse in others (e.g. multi-armed bandits), and are the first of their kind in other settings (e.g., RL with general function approximation).

Strengths

The problem of delayed feedback in online learning settings is a well-motivated problem with many real-world applications. Furthermore, the authors are the first to obtain results for learning with delayed feedback in a variety of (important) settings such as RL with general function approximation, as well as improve upon existing results in others such as linear bandits. The two main strengths of this paper are the simplicity/clarity of the proposed framework and the sheer number of results the authors are able to obtain using their framework. It is impressive that results for so many important settings are able to be obtained by applying one simple framework. Moreover, all that is required to use their framework is a multi-batched algorithm, which already exist in the literature for many online learning settings.

Weaknesses

At times, the writing feels a bit rushed and as a result the submission may be a hard read for someone who is not an expert in RL theory. Specifically, I felt that the mutli-agent results were somewhat lacking in detail. (For example, why is the CCE the "right" solution concept, what happens when all players do/don't play a CCE policy, etc.) This is probably due to the fact that the authors have lots of results, which they wish to highlight in the main body of the paper. One suggestion would be to move either subsection 5.1, 5.2, or 5.3 to the Appendix, and use the extra space to provide more background/detail/hand-holding for the reader.

Questions

I was a bit confused by the notation in line 9 of Algorithm 2. Shouldn't this read (both in words and mathematically) "Collect trajectory feedback in this batch that is observed **by** the end of the episode"? Would your framework be able to obtain stronger results if, instead of Assumption 2, the delays are assumed to be subGaussian random variables? A reference is missing to "Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning" by Huang et al.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations of their work.

Summary

The paper presents a new framework for handling stochastic delayed feedback in general sequential decision-making problems, encompassing bandits, single-agent Markov decision processes (MDPs), and Markov games (MGs). The authors introduce a novel reduction-based framework that converts any multi-batched algorithm for sequential decision-making with instantaneous feedback into a sample-efficient algorithm capable of managing stochastic delays. They provide various examples, demonstrating the efficacy of their framework in different scenarios, and present several new results, improving existing findings for linear bandits, tabular RL, and tabular MGs.

Strengths

The paper addresses a significant and practical issue in sequential decision-making: stochastic delayed feedback. It is well-motivated with practical examples like recommendation systems, robotics, and video streaming. The paper presents a novel, reduction-based framework that shows versatility across multiple domains (bandits, single-agent MDPs, and MGs), exhibiting a comprehensive approach. The proposed solution offers theoretical advancements by improving the regret bounds for linear bandits and tabular RL and provides the first theoretical guarantees in RL with function approximation and multi-agent RL settings. The authors effectively integrate existing multi-batched algorithms into their framework, illustrating the generality of their approach.

Weaknesses

It seems that the contribution is rather incremental. The idea that multi-batched algorithms can be used in delayed setting is not new. What appears to be new is some new theorems bounding the regret when using multi-batched algorithms for delayed settings in a variety of settings. The authors could strengthen their paper with some simple experiments to add to the theory

Questions

Can you elaborate more on the specific limitations of the current state-of-the-art methods that your framework is intended to overcome? Can your framework be generalized to handle other types of delays, or is it specifically designed for stochastic delays?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Can we develop new algorithms that work even better than existing multi-batch algorithms? The paper leaves open the question of whether their results are tight for MDP and MG with delayed feedback. Thus, there is room for future work to tighten these results. The paper suggests that a multi-batched algorithm with a smaller batch number for tabular Markov games could be derived, which may provide more efficiency, but does not provide it in this paper. It remains unclear if their findings and the proposed framework will translate effectively into practical scenarios. The authors have not provided any real-world evaluations or use-cases to support their claims.

Summary

This paper provides a general framework for analysing any ‘mini-batch’ or rarely switching algorithm in the presence of delayed feedback. This approach covers bandits, finite horizon MDPs and finite horizon Markov games. The results provided match or improve on the best-known results for delayed feedback in settings that have been studied before, and provide the first bounds in some settings where delayed feedback has not been studied before.

Strengths

It is nice to have a comprehensive study of delayed feedback in various settings. It is interesting that phase-based algorithms allow one to deal with delayed feedback effectively in a variety of settings. It is nice that the general framework provided in this paper allows us to recover the same bounds as for algorithms for specific settings and provides new bounds in settings where delayed feedback has not been studied previously.

Weaknesses

The writing and clarity could be improved. I also found the structure quite confusing with a couple of pages dedicated to Markov games while a lot of the content needed to understand that section (e.g. related work and algorithms) relegated to the appendix. The amount of space dedicated to Markov games also meant that there was not sufficient room to discuss the results for delayed feedback in bandits/RL, nor for all details of the method/results to be provided (see the many questions below). The idea of using phase-based algorithms which switch arms less frequently for delayed feedback is not new and has been used in e.g. Lancewicki et al (2021), Howson et al (2021), Pike-Burke et al (2018), Vakili et al (2023),… This should be stated in section 4. Additionally, I believe Vakili et al (2023) also provide the same bound for the linear bandit setting with delayed feedback as is established in this paper, so this should also be checked and added. References: Vakili, Sattar, et al. "Delayed Feedback in Kernel Bandits." ICML, 2023. Pike-Burke, Ciara, et al. "Bandits with delayed, aggregated anonymous feedback." ICML, 2018

Questions

The two results in e.g. theorem 1 are a bit confusing and the difference between them is not well explained. Is the second one (7) on the expected regret and the first (6) on the high probability regret? For (6), I am assuming that q is a parameter which can be chosen, can any guidance be provided for how to choose it? Does it depend on \delta? I am interested in whether experimentally these rarely switching algorithms actually perform better than algorithms tailored to the specific setting, or just versions of optimistic algorithms that only use available data? A couple of times ‘minimax optimal’/’tight’ is stated. Are there lower bounds for all these settings with delayed feedback? Can the lower bounds/best results for the non-delayed settings be added to the table of results to enable us to clearly understand what the impact of delayed feedback is? In the general algorithm provided in section 4 and algorithm 2, do we need to know the delay distribution to define the batch lengths? The example in the text would suggest that we do, but the pseudo-code does not mention it. In the introduction it is mentioned that the sub-exponential assumption on the delay distribution is only sometimes needed, yet I cannot find any discussion of when it is used for the main results. Is it needed for all results in Theorem 1?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Very brief discussion of limitations in conclusion

Response to Authors

Thanks for clarifying the contributions. After reading the rebuttal and the other reviews I wouldn't be opposed to voting for acceptance if the authors can include additional discussion about the contribution in the camera-ready paper.