A Unified Model and Dimension for Interactive Estimation

Summary

This paper studies a general interactive learning setting, which is termed "interactive estimation". In this model, we are given a set of alternatives, which contains the target. At each step, the learner can choose an alternative and receive the similarity of this alternative with the target. Based on this input, the goal is to get as close as possible to the target. The authors then demonstrate that many well studied settings are special cases of this general framework, including structured bandits and SQ learning. Then, they introduce a novel combinatorial parameter which they call "dissimilarity dimension". They prove that a general algorithm which, under reasonable assumptions, has regret that is bounded by a polynomial of the dissimilarity dimension. Furthermore, they show that the dissimilarity dimension is polynomially related to the strong SQ dimension, which automatically gives lower bounds in the sample complexity in terms of the dissimilarity dimension. Lastly, they prove that the dissimilarity dimension is upper bounded by the Eluder dimension and give concrete examples where the gap between the two is quite wide, which yields improved regret analysis for some bandit settings.

Strengths

Overall, the contributions of this paper are novel and highly relevant for the learning theory community. In terms of results, both definitions of the interactive estimation setting and the dissimilarity dimension are valuable contributions of this work. It is interesting that one can define such a general setting that encompasses various seemingly unrelated problems and still provide a meaningful combinatorial measure of complexity that characterizes learnability under general conditions. The fact that studying the dissimilarity dimension results in tightening various existing results about specific bandit settings is also an important feature of this work, and it seems to open up unexplored directions of research in this well-established field. Another important aspect of this work is that it provides an algorithmic template, which can be instantiated using various algorithms that exist in the literature. On the technical side, the main proofs contain novel and non-trivial ideas, such as the idea of using Turan's Theorem to bound the number of bad queries in terms of the dissimilarity dimension in Lemma 5. In terms of presentation, the paper is very well written, with all key ideas explained clearly and succinctly. It is also nice that the authors try to give intuition for the important ideas that are involved in proving the Theorems, such as the intuitive reason for why the dissimilarity dimension is "tighter" than the Eluder dimension (before Proposition 12).

Weaknesses

The main weakness in terms of results is the decaying estimation assumption, which is crucial in order for Algorithm 1 to work. The authors provide several alternative assumptions which imply the decaying estimation, such as the existence of an online regression oracle with sublinear regret, or bounded covering numbers for the set of alternatives. While these are reasonable assumptions that have been used in many settings in prior work, it would be interesting to see whether they can be relaxed, or whether they are somehow related to the assumption of boundedness of the dissimilarity dimension. Right now there is no discussion in the paper about that relation.

Questions

-One question, which is also briefly discussed by the authors, involves the computational complexity of the proposed algorithms. In particular, are there some interesting conditions for the similarity measure $\rho$, under which the least squares optimization of Algorithm 1 can be implemented in polynomial time? -It is implicitly assumed that for any given $z_1,z_2 \in \mathcal{Z}$, the algorithm can compute $\rho(z_1|z_2)$. This is certainly the case in the specific settings of SQ learning and structured bandits, which are studied in the paper, but one could imagine situations where that computation is not possible. Would it be possible to impose some conditions on $\rho$ which still enable learning of the target, without having access to an evaluation oracle for $\rho$?

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

4 excellent

Contribution

3 good

Limitations

Yes, the limitations have been adequately addressed.

Summary

In this work the authors introduce a framework for interactive estimation, where the learner interacts with some oracle that provides information in the following way: the learner submits a query $z$ and the oracle returns a stochastic reward whose mean is given by a measure of dissimilarity between the query and the ground truth. The main benchmark they care about is the regret guarantees that the learner can achieve. The authors propose a dimension which they call the dissimilarity dimension whose finiteness provides a sufficient condition for learnability in this model. They also propose an algorithm based on the least-squares method that achieves sublinear regret when the dissimilarity dimension is finite. Then, they also describe an online-to-batch conversion that can be used to establish learning guarantees in the offline setting. Moreover, they show how their framework can be instantiated to capture the SQ learning setting and the structured bandit setting. Finally, they illustrate learning tasks for which their approach yields sharper bounds than the state of the art.

Strengths

* The authors are studying fundamental learning problems and any new perspectives which lead to better results in this line of work should be welcome. * The dissimilarity dimension can be viewed as a more localized version of the eluder dimension, which as the authors show, can lead to better bounds than the latter. * It is always interesting to try to unify settings, but I have some doubts about this unification (see Weaknesses/Questions). * Even though the techniques build upon the prior work, they are not trivial. * This dimension could have applications in other settings as well. * The paper is well-written and easy to follow, I particularly enjoyed the comparison with the eluder dimension and the explanation about the improvement that the dissimilarity dimension yields.

Weaknesses

* My main concern is that the unification that the authors propose under this framework feels a bit forced and not very natural. In particular, in the model the authors propose the learner queries a point $z_t$ in every round $t$ and gets a stochastic reward whose mean is $\rho(z_t|z^\star)$, where $z^\star$ is the ground truth and $\rho$ can be thought of as a dissimilarity measure. In order to get the results in the bandit setting, they let $z = (a, f)$, where $a$ is some arm and $f$ is some reward function that maps arms to rewards. This does not feel very natural because the traditional way to think of this setting is that the learner queries arms, and not arms and functions. Moreover, the way the distance function is defined is $\rho_{bandits}((f,a)|(f^\star,a^\star)) = f^\star(a)$, so we can see that both $a^\star, f$ do not affect its value. It seems as if it was defined this way in order to make the definition of the dissimilarity measure work, but it does not exactly convey the message it was supposed to. Am I missing something? * Line 50: "Largely characterizes learnability in our setting". This is a bit vague and inaccurate. I don't understand what it means for a dimension to "largely characterize" learnability, since it either characterizes it or it doesn't. What you have shown is that finite dissimilarity dimension implies learnability, and that there are instances with infinite such dimension that are not learnable. However, there could be problems whose dissimilarity dimension is infinite, by they are still learnable.

Questions

* What is the intuition behind the scaling of the distance in definition 1 by $\sqrt{d}$? * The example in Proposition 12 is certainly interesting, but are you aware of some more "natural" settings where the dissimilarity dimension can be finite whereas the eluder dimension is infinite? * Can you derive logarithmic regret bounds that depend on some notion of suboptimality gap? For instance, in the context of bandits that would be the gap between the reward of the best arm and the second best arm. * Can the results be extended to contextual bandits and RL? A long line of work has established strong connections between the eluder dimension and regret bounds in various RL settings.

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

The paper introduces a learning model where an unknown target exists, and in each round, the learner selects a choice and receives a stochastic feedback indicating the similarity between the choice and the target. The objectives examined involve minimizing regret or providing a PAC-style guarantee, ensuring that a choice with approximately maximum similarity to the goal is returned with high probability. This model encompasses both bandits and correlational statistical query algorithms. The paper introduces the concept of "dissimilarity dimension", a combinatorial measure that captures the learnability within the model. It proves that the dissimilarity dimension implies learnability and can be achieved by any algorithm satisfying two properties: (i) selecting choices with high similarity to themselves and (ii) improving the quality of reward estimates over time. The paper presents a simple algorithm that satisfies these properties, demonstrating that it achieves bounded regret and a PAC generalization guarantee. In terms of the connection to the statistical query (SQ) model, the paper establishes that the dissimilarity dimension is polynomially related (both in upper and lower bounds) to the “strong SQ dimension”. Additionally, regarding the connection to bandits, the paper demonstrates that the dissimilarity dimension is upper bounded by the eluder dimension, which is commonly used in bandit problem literature. The paper provides concrete examples of bounding the dissimilarity dimension for bandit problems and illustrates cases where the dissimilarity dimension is significantly smaller than the eluder dimension.

Strengths

The paper introduces a novel learning protocol and presents a combinatorial dimension that captures learnability. Furthermore, it establishes connections between this dimension and two extensively studied learning models. The fact that the proposed dimension can be much smaller than the existing eluder dimension is particularly interesting and perhaps surprising result. The work is original and novel, and I would be happy to recommend acceptance.

Weaknesses

I do not see any strong weaknesses.

Questions

I was under the impression that the results in Szörényi 2009 hold for real-valued hypotheses as well. Is there a particular reason why Section 4 restricts to binary classifiers?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

Addressed.

Summary

This paper presents a novel unified framework for interactive estimation. The framework involves a learner making repeated queries to the environment and observing rewards that correspond to the similarity between the query and an unknown target. The algorithm then uses these observed signals to estimate the target. This general framework for interactive learning is connected to two instantiations of learning models: the SQ model and structured bandits, which are studied in this paper. Additionally, a new combinatorial dimension is proposed to measure the difficulty of learning, and it is used to offer standard analysis to achieve tighter regret bounds.

Strengths

The paper has several notable strengths. It proposes a new unified framework for interactive estimation and a novel dimension called dissimilarity dimension to measure hardness. It connects two classical frameworks and offers the analysis with them, then finds with their proposed dimension, tighter regret bound can be achieved. Furthermore, it shows another possible to rely on the proposed dissimilarity measure.

Weaknesses

Here are some potential improvements to the original content: 1. The writing sometimes is too abstract to understand the concept (Introduction) and hard to follow (Section 3 Algorithm). It can be beneficial if more explanation and practical settings are provided. 2. The completeness of the framework can be further enhanced through additional empirical experiments.

Questions

1. Why do we need a new dissimilarity measure and the intuition behind it? I am curious about the difference between it and typical approach as dissimilarity measurement. 2. Since this framework claims to be unified to many settings, is there any experiment we can validate its universal feature?

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 introduces a unified framework for interactive learning that has the potential to be applied in various scenarios. It also establishes connections with two classical models to demonstrate its impact and applicability. The completeness of the framework can be further enhanced through additional empirical experiments.

Questions

Dear Reviewer, We would like to know if this explanation made sense? If it did and it addresses the reviewer's concerns, we would very much appreciate if the reviewer could reassess their score to one that reflects this renewed understanding. We hope the discussion with other reviewers has also helped address any lingering concern. Thanks a lot!