Provably Efficient Interactive-Grounded Learning with Personalized Reward

Summary

This paper considers Interactive-Grounded Learning (IGL) with personalized reward, where the feedback can be context-dependent. The authors propose two algorithms, which are provably efficient by utilizing the novel Lipschitz reward estimators. Empirical results on the image classification dataset and the conversational dataset showcase the effectiveness of the proposed algorithms.

Strengths

(+) This is the first work to provide provably efficient algorithms with regret guarantees for IGL with personalized reward. (+) It is interesting to see the experiments on the conversation dataset, which is a novel task in the IGL literature.

Weaknesses

(-) The paper does not compare the proposed algorithms to the IGL-P algorithm proposed in (Maghakian et al., 2022). (-) While there are justifications in the paper for using the Lipschitz reward estimators (Lemma 4), it is unclear why using $\mathbb{1}\\{\hat{h}_a(x,y)\ge\frac{\theta}{\alpha}\\}$ or the previous IGL-P algorithm could fail.

Questions

1. It would be nice to provide counter-examples to show why using $\mathbb{1}\\{\hat{h}_a(x,y)\ge\frac{\theta}{\alpha}\\}$ or the step-function estimator in prior work could fail in the setting. 2. How restrictive is it to obtain prior knowledge of parameters $\alpha$ and $\theta$ in Algorithms 1 and 2? What is the role of parameter $\gamma$ in Algorithm 2?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

No "Limitations" section is provided in the paper.

Summary

This paper studies the problem of personalized rewards in the context of Interactive-Grounded Learning (IGL), where the goal is to maximize the unobservable latent rewards from the observed reward-dependent feedback on actions being taken. Specially, authors introduce provably efficient algorithms with sublinear regret to solve a variant of IGL, in which the feedback depends on both the context and rewards. Authors introduce Lipschitz reward estimator via inverse kinematics. Based on it, two algorithms are proposed based on explore-then-exploit and inverse-gap weighting respectively. Both achieves $O(T^{2/3})$ regret. Empirical studies are performed on an image classification dataset and a conversational dataset.

Strengths

This paper explores a variant setting of IGL. Instead of sticking with the conditional independence assumption made in existing works, authors go one-step further by studying the setting where the observed feedback depends on both rewards and the context. This setting is practical in cases such as recommender systems. The authors introduces two algorithms that enjoy the sublinear regret of $\tilde{O}(T^{2/3})$ for IGL with personalized reward. In particular, a new reward estimator is introduced via inverse kinematics to construct Lipschitz rewards. Compared to the prior work (Maghakian et al., 2022) which studies deterministic binary reward, here the reward estimator generalizes to randomized binary rewards.

Weaknesses

While this paper clearly articulates the idea, my main concern lies in its technical novelty and contribution. More specifically, 1. While I understand the motivation of the paper, It is not clear to me how the studied setting can be technically more challenging than the common contextual bandits. The studied setting concerns about partial feedback that depends on latent reward and context, whereas contextual bandits concerns about explicit rewards that depend on context and action. The studied setting is somewhat a simplified version of POMDP. As such, extending the stochastic contextual bandit algorithms and their theoretical guarantees for IGL appears to be straightforward. 2. Prior study of Xie et al. [2022] has relaxed the conditional independent assumption to study feedback which depends on both action and reward. A natural extension will be to deal with feedback that depends on context, action, and reward (i.e. $y|x, a, r$) when it comes to the personalized settings. It is also more practical and align with the contextual bandit settings. However, authors preserves the conditional independent assumption for actions. 3. The main contribution and emphasis lies in the construction of the reward estimator, the novelty in algorithmic design appears to be limited by using simple standard bandit algorithms (e.g. explore-then-exploit). In addition, algorithmically, employing uniform exploration may lead to higher sample complexity for the balance between exploration and exploitation. More advanced exploration strategies might need to be considered. As such, authors are suggested to comment on the optimality of the provided regret bound. 4. Compared to Algorithm 1, the performance guarantee of Algorithm 2 relies on more restricted assumptions (Assumptions 1 - 5), which can be difficult to satisfied.

Questions

1. Could you explain why do we need an underestimate of the reward in this studied setting? Most of the time when we study online settings, optimism is desirable. 2. What is the intuition of $\sigma$? 3. In Table 1, why the performance of algorithm 2 outperforms algorithm 1? Do they converge to similar performance if running for longer time horizon? It is suggested to provide the regret plots for experiments.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

No potential negative social impact.

Summary

In this work, the authors provide the first provably efficient algorithms with sublinear regret guarantees for Interactive-Grounded Learning (IGL) with personalized rewards under realizability. Based on a novel Lipschitz reward estimator, the authors propose two algorithms: one based on explore-then-exploit and the other based on inverse-gap weighting. Furthermore, the authors apply IGL to learning from image feedback and learning from text feedback, showcasing the effectiveness of the proposed algorithms.

Strengths

This work provides the first provably efficient algorithms for Interactive-Grounded Learning with personalized rewards, supported by experiments demonstrating the effectiveness of the proposed algorithms. The presentation is generally clear, with detailed experiment settings, and the appendix is well-organized. The definitions and assumptions are well defined.

Weaknesses

The theoretical contributions are limited by the realizability and identifiability assumptions. It would be helpful to provide practical examples where all these assumptions are satisfied. In Table 1, the difference between Binary and Lipschitz reward estimation seems insignificant, which raises doubts about the practical contribution of the new estimator.

Questions

Same as weakness. Q1: It seems straightforward to apply explore-then-exploit and inverse-gap weighting. Could you please state the challenges encountered when proving the regret guarantees? Q2: It would be helpful if the authors could provide some related lower bounds to help readers understand the gap between the current regret bound and the optimal rate.

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

2

Limitations

Same as weakness.

Summary

The authors provide sublinear regret algorithms for Interaction Grounded Learning (IGL) setting, a modification of the standard contextual bandit setting where instead of getting the reward signal, the learner receives some alternative signal from an arbitrary space. The game proceeds for T rounds where at every round, the learner gets a context x_t, chooses an action a_t, gets a reward r(x_t, a_t) and receives feedback y_t \in Y. The primary difference from the prior work is that the reward function can depend on the context x, i.e. the reward function can be personalized for the context x. Due to this personalization, the authors make an independent assumption that given the reward and the context, the observation and the action are independent to each other.

Strengths

Provide T^{2/3} style of regret bounds for IGL setting with personalized rewards. Most of the assumptions and problem setting follow classical contextual bandits literature. Experimental are provided for the corresponding algorithms.

Weaknesses

The regret bound scales as T^{2/3} and it is not clear how or when can we get T^{1/2}. I am guessing that similar to the partial monitoring setting we will need to make assumptions on the function \Phi and there will be a dichotomy between T^{1/2} regret vs T^{2/3} regret based on the information structure. The proof techniques follow closely well-known tools like inverse kinematics and SquareCB from the contextual bandits and RL literature. However, the experiments are still quite interesting.

Questions

Can the authors provide a more detailed discussion of how IGL is different from the partial monitoring setting. From what I understand, the primary difference is the assumption that learner has access to a class \Phi which contains a decoder \phi that maps the context and observation to actions. Thus this becomes closed to Model-Based methods in RL, etc, and hence we can expect statistical traceability. Can the authors elaborate if there are any other differences? Paper is well written.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

NA

Follow-up Response

I thank the authors for their responses to my questions. I appreciate that they include numerical results on the comparison with the IGL-P algorithm. Responding: **Q1.** For interpretability, in the later version of the paper, I would suggest plotting the empirical errors of $\mathbb{1}\{\hat{h}_a(x,y)\geq\frac{\theta}{\alpha}\}$ and $G(\hat{h}_a(x,y),\frac{\theta}{\alpha}-\sigma,\sigma)$ compared to the ground-truth estimator $\mathbb{1}\{h_a^\star(x,y)\geq\frac{\theta}{\alpha}\}$.