Online Learning with Gaussian Payoffs and Side Observations
We consider a sequential learning problem with Gaussian payoffs and side observations: after selecting an action i, the learner receives information about the payoff of every action j in the form of Gaussian observations whose mean is the same as the mean payoff, but the variance depends on the pair (i, j) (and may be infinite). The setup allows a more refined information transfer from one action to another than previous partial monitoring setups, including the recently introduced graph-structured feedback case. For the first time in the literature, we provide non-asymptotic problem-dependent lower bounds on the regret of any algorithm, which recover existing asymptotic problem-dependent lower bounds and finitetime minimax lower bounds available in the literature. We also provide algorithms that achieve the problem-dependent lower bound (up to some universal constant factor) or the minimax lower bounds (up to logarithmic factors).
The authors consider a sequential decision problem in stochastic environment with Gaussian payoffs and Gaussian side observations. In each time step a learner chooses an action from a fixed finite set of actions, receives a random reward associated with the action, and observes a feedback from other actions. All the observation are Gaussian random variables with fixed expectations and variance depending on a chosen action. The setting includes several previously studied feedback models: full information, bandit, and partial monitoring with feedback graphs (previously studied in adversarial environment).The setting of the paper is very interesting and naturally extends previous settings, which provides tools to capture problems with complicated feedback structure.Pros of the paper:The main contribution of the paper are lower bounds on the regret for any algorithm. The authors provide non-asymptotic problem-dependent lower bound, which recovers asymptotic problem-dependent lower bound, and finite-time minimax lower bound.The authors proposed two algorithms and their finite-time analysis. The first algorithm achieves upper bound which matches asymptotic problem-dependent lower bound (up to constants) and the second algorithm achieves upper bound which matches minimax lower bound (up to logarithmic factors).Cons of the paper:Even though the setting provides rich feedback structures, the upper bounds for the algorithms are analysed only for a special case of uniform variance, where the variance terms are equal to either sigma or infinity (feedback graphs). In particular, the proofs of Theorem 6 andTheorem 8, provided in appendix B and C(proved using standard tools) are only considering this special case and it is unclear if the approach would extend to the general case which seems more interesting. However, my main objection is that the paper lacks intuition behind the proofs (especially for the lower bound). A good example is Section 3.2.1.: There is no reason given why are the quantities defined as such. What does the set of the reasonable items mean? Where are the definitions for m_i^+ and m_i^- coming from? The whole Section 3.2.1. is extremely hard to parse and features almost no explanations or relations to the studied problem.With regards to the lower bound, it is also unclear whether this is indeed the difficult case, since the upper-bound for the nonuniform case is not given.Furthermore, there is a significant amount of mistakes, including wrong or missing indices. Examples: assumption (iii) in section 2, simplex using set C_N^T as upper index insection 3.1), missing terms (e.g. definition of C_T in section 2.1)). Combined with missing descriptions of the ideas, this makes it even harder toto follow the paper.Conclusion:Even though the results in the paper are substantial, the paper needs significant changes to eliminate mistakes, provide intuition behind (mostly the lower bound) proofs, improve clarity and readability.Therefore in my opinion, the paper is not ready to be published in the current form.