Summary
This paper studies a variant of the recently proposed framework of Foster et al. for sequential decision making, based on a concept called "decision estimation coefficient" (DEC). The variant proposed here is based on enhancing the estimation step in the "estimation-to-decisions" (E2D) with an optimistic bias inspired by the recent work of Zhang. The authors show that this biased estimation scheme, coupled with an appropriately adjusted decision-making rule, can satisfy very similar regret guarantees for a wide range of sequential decision problems, and can provide improvements in certain settings. In particular, the authors show that their approach can handle a large class of tractable models for reinforcement learning called "bilinear classes".
Strengths
The paper is well-written and the technical content is of excellent quality. The proposed approach is justified and explained well, and its analysis is also presented in an accessible way (at least on a high level). While the regret bounds for bilinear MDP classes is not novel in the sense that there exist other algorithms that achieve the same guarantees, I appreciate the conceptual contribution of showing that the DEC framework is also capable of tackling these (relatively) challenging problems.
I appreciated the very careful comparison between all the relevant DEC variants in Section 3: the authors didn't just propose a technique and proved some bounds about it, but also explored a range of other opportunities and explained the differences between them in an accessible manner.
Weaknesses
On the negative side, the rates that the authors derive are not particularly great: the scaling goes from $T^{2/3}$ in the setting with the most stringent assumptions all the way to $T^{5/6}$ as more and more assumptions are dropped. While the authors discuss this limitation quite openly, I would have appreciated some more discussion as to where this relatively poor scaling comes from. One contributing factor is certainly the use of batched estimation steps. My understanding is that some further looseness may come from the optimistic bonuses added to the estimation procedure, which makes the total estimation error grow polynomially with the number of updates (as opposed to logarithmically, which would allow getting sqrt{T} rates after putting everything together). I wonder though if this intuition is correct, and I would appreciate it if the authors could clarify what rate they would get if they could afford to set n=1 (without paying for it). Altogether, it would have been nice if the to compare the various notions of estimation error with the same care as what the DEC variants have received.
Overall, I am leaning towards suggesting acceptance, but I would feel more strongly about my support if the authors were able to address my questions above in a satisfying way.
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.