Provably Efficient Interactive-Grounded Learning with Personalized Reward

Authors: mengxiao  zhang
yuheng  zhang
haipeng  luo
paul  mineiro
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:07:59

Abstract: Interactive-Grounded Learning (IGL) [Xie et al., 2021] is a powerful framework in which a learner aims at maximizing unobservable rewards through interacting with an environment and observing reward-dependent feedback on the taken actions.
To deal with personalized rewards that are ubiquitous in applications such as recommendation systems, Maghakian et al. [2022] study a version of IGL with context-dependent feedback, but their algorithm does not come with theoretical guarantees. In this work, we consider the same problem and provide the first provably efficient algorithms with sublinear regret under realizability. Our analysis reveals that the step-function estimator of prior work can deviate uncontrollably due to finite-sample effects. Our solution is a novel Lipschitz reward estimator which underestimates the true reward and enjoys favorable generalization performances. Building on this estimator, we propose two algorithms, one based on explore-then-exploit and the other based on inverse-gap weighting. We apply IGL to learning from image feedback and learning from text feedback, which are reward-free settings that arise in practice. Experimental results showcase the importance of using our Lipschitz reward estimator and the overall effectiveness of our algorithms.

Main paper: 
 introduction: 
 Traditional bandit problems [Auer et al., 2002] or reinforcement learning problems [Sutton and Barto, 2018] assume that the learner has access to the reward, which is her learning goal. However, such explicit reward information is usually difficult to obtain in many real-world scenarios, including human-computer interface applications [Pantic and Rothkrantz, 2003, Freeman et al., 2017] and recommender systems [Yi et al., 2014 , Wu et al., 2017] . Recently, Xie et al. [2021] study a new setting called Interaction-Grounded Learning (IGL), where the learner interacts with the environment and receives some feedback on her actions instead of explicit reward signals. The learner needs to discover the implicit information about the reward in the feedback and maximizes the reward.From an information-theoretic perspective, IGL is intractable unless further assumptions are made. Xie et al. [2021] introduce a conditional independence assumption which states that the feedback is conditionally independent of the action and context given the latent reward. However, this assumption is unrealistic in many scenarios. For example, different users interact with recommender systems in different ways even under the same latent reward [Maghakian et al., 2022] . This inspires us to study IGL with personalized rewards, a setting where the feedback depends on the context. Although Maghakian et al. [2022] study this for recommender systems, they only provide empirical results of their approach, leaving the following question open:Can we design provably efficient algorithms for interaction-grounded learning when the feedback depends on the context given the latent reward?Contributions. In this paper, we answer the question in the positive and provide the first provably efficient algorithms with sublinear regret guarantee for IGL with personalized reward. To achieve this, in Section 3.1, we first propose a novel reward estimator via inverse kinematics. Specifically, using the samples collected by applying a uniform policy, we construct a Lipschitz reward, which underestimates the reward for all the policies but approximates the reward for the optimal policy well. With this reward estimator, we propose two algorithms, one based on Explore-then-Exploit (Section 3.2) and the other based on inverse-gap weighting (Section 3.3). Both algorithms achieve O(T3 ) regret. To the best of our knowledge, we are the first to propose provable regret guarantees for IGL with personalized reward. In Section 4, we implement both algorithms and apply them to both an image classification dataset and a conversational dataset. The empirical performance showcases the effectiveness of our algorithm and the importance of using the Lipschitz reward estimator.Interaction-Grounded Learning (IGL). Xie et al. [2021] is the first work studying IGL and assumes that the feedback is independent of the context and action conditioned on the latent reward. Xie et al. [2022] further relaxes the assumption to an action-inclusive version, where the feedback is independent of context conditioned on both the action and the reward. 2 Hu et al. [2024] follows the same setting as Xie et al. [2021] but proposes an information-theoretic approach to enforce the conditional independence assumption. However, as we mentioned before, context-dependent feedback is ubiquitous in real-word applications, so such conditional independence assumptions reduce the generality of the IGL framework. Maghakian et al. [2022] is the closest work to ours which also considers personalized rewards. Nonetheless, their work focuses on the empirical side and does not provide any theoretical guarantees.Contextual online learning with partial feedback. Our work is closely related to the recent trend of designing efficient contextual learning algorithms with partial feedback, including contextual bandits [Langford and Zhang, 2007 , Agarwal et al., 2012 , 2014 , Foster and Krishnamurthy, 2018 , Foster et al., 2018 , Foster and Rakhlin, 2020 , Simchi-Levi and Xu, 2021] , where the learner receives explicit reward signal of her taken action; contextual bandits with feedback graphs [Zhang et al., 2024a,b] , where the learner's observation of the reward is determined based on a feedback graph; and contextual partial monitoring [Bartók and Szepesvári, 2012, Kirschner et al., 2020] , where the learner's observation is defined by a signal matrix or a linear observation operator. We adopt and generalize the ideas for designing contextual bandits algorithms [Foster and Rakhlin, 2020] to design algorithms for IGL. 
preliminary: 
 Problem setup. Throughout the paper, we use [N ] to denote the set {1, 2, . . . , N } for a positive integer N . The problem of online Interative-Grounded Learning (IGL) with personalized reward we consider is defined as follows. The interaction between the learner and the environment lasts for T rounds. At each round t ∈ [T ], the environment reveals a stochastic context x t ∈ X i.i.d. drawn from an unknown distribution D, and the learner decides an action a t ∈ [K] from a finite action set of size K based on this context. Then, different from the classic contextual bandits in which the learner observes the binary reward of her chosen action r(x t , a t ) ∈ {0, 1}, she receives feedback y t ∈ Y.Feedback dependence assumption. We follow the assumption proposed in [Maghakian et al., 2022] that the feedback is conditionally independent of the action given the context and the realized reward. Assumption 1. For arbitrary (x, a, r, y) tuple where the reward r and the feedback y are generated based on the context x and action a, we assume y is conditionally independent of action a given context x and reward r. In other words, we assume that y ⊥ a | r, x.As mentioned, compared to prior work [Xie et al., 2021 [Xie et al., , 2022]] , this better captures many real-world applications such as recommender systems where different users interact with them in different ways [Beel et al., 2013 , Shin, 2020 , Maghakian et al., 2022] .Realizability. We assume that the learner has access to two function classesF ⊆ (X ×[K] → [0, 1]) and Φ ⊆ (X × Y → {0, 1}), where F characterizes the mean of the reward for a given contextaction pair, and Φ characterizes the realized reward given the context and the received feedback. A policy π : X → ∆(K) specifies the action probability conditioned on the context. For each f ∈ F, we use π f to denote the induced policy which takes action greedily according to f , that is,π f (a|x) = 1{a = argmax a ′ ∈[K] f (x, a ′ )}, ∀a ∈ [K].We also use the shorthand π ⋆ for the optimal policy π f ⋆ . We then make the following realizability assumption following previous contextual bandits literature [Agarwal et al., 2012 , Foster et al., 2018 , Foster and Rakhlin, 2020 , Simchi-Levi and Xu, 2021] . Assumption 2 (Realizability). There exists a regression functionf ⋆ ∈ F such that E[r(x t , a)|x t ] = f ⋆ (x t , a) for all a ∈ [K] and t ∈ [T ]. Furthermore, there exists a feedback decoder ϕ ⋆ ∈ Φ such that ϕ ⋆ (x t , y t ) = r(x t , a t ) for all t ∈ [T ].For simplicity, we also assume that F and Φ are finite with cardinality |F| and |Φ|. Our results can be further generalized to broader function classes, which will be discussed in later sections.Identifiability. As mentioned in [Xie et al., 2021 , 2022 , Maghakian et al., 2022] , it is impossible to learn if we do not break the symmetry between reward being 1 and being 0. Following [Maghakian et al., 2022] , we make the following assumption: Assumption 3 (Identifiability). For any x ∈ X , f ⋆ defined in Assumption 2 satisfies that: 1)K a=1 f ⋆ (x, a) ≤ α for some 0 < α < K 2 ; 2) max a∈[K] f ⋆ (x, a) ≥ θ where θ > α K-α .The first condition says that the sum of the expected reward over actions is less than K 2 given any context x. That is to say, the reward vector is sparse if f ⋆ (x, a) ∈ {0, 1}. The second condition says that for each context x ∈ X , there exists an action that achieves a large enough expected reward. These two conditions are indeed satisfied by many real-world applications, including the s-multi-label classification problem (with s < K/2) where α = s and θ = 1.Regret. The learner's performance is measured via the notion of regret, which is defined as the expected difference between the learner's total reward and the one received by the optimal policy:Reg CB = E T t=1 f ⋆ (x t , π ⋆ (x t )) - T t=1 f ⋆ (x t , a t ) ,Other notations. We denote the (K -1)-dimensional simplex by ∆ K . Let 1 be the all-one vector in an appropriate dimension andπ Unif = 1 K • 1 ∈ ∆ K . For a d-dimensional vector v ∈ R d , wedenote its i-th entry by v i . 1{•} is the indicator function and e i is the i-th standard basis vector in an appropriate dimension. 
methodology: 
 In this section, we discuss our methodology. In Section 3.1, we start from introducing how we construct a Lipschitz reward estimator based on uniform samples, which serves as the key for our algorithm construction. We prove that this estimator is an underestimator of the reward, and more importantly matches the reward for the optimal policy. Based on this estimator, we design two algorithms for this problem in Section 3.2 and Section 3.3, with the first one based on explore-thenexploit and the second one based on inverse-gap weighting (IGW).We first show how we construct a reward estimator based on feedback collected from a uniform policy, which serves as the most important component in our two algorithms.When the reward for each context-action pair is deterministic and binary, Maghakian et al. [2022] show that if the learner uniformly samples an action for any context and is able to accurately predict the posterior probability of her chosen action given the context and the feedback (inverse kinematics), then she is able to infer that the reward is 1 if that posterior probability is above certain threshold.Here, we generalize this thresholding reward estimator to the randomized binary reward case, and further prove that this estimator correctly models the reward for the optimal policy. To see this, we first prove the following lemma showing the exact posterior distribution over actions if the learner selects an action uniformly randomly. This is also proven in [Maghakian et al., 2022, Eq. (2)] as well, and we include it here for completeness. Lemma 1. For any context x ∈ X , suppose that the learner picks a uniformly random action a ∈ [K].Let r and y be its realized reward and the corresponding feedback. Then, under Assumption 1 and Assumption 2, the posterior distribution of a given the context x and feedback y equals toEQUATIONwhere f ⋆ and ϕ ⋆ are the true expected reward and feedback decoder defined in Assumption 2.Now we show how to infer the true reward from this inverse kinematics. Specifically, we show: Lemma 2. For any context x ∈ X and action a ∈ [K], let r(x, a) be the realized reward and y be the feedback. Let h ⋆ (x, y) ∈ ∆ K be such that for each a ∈[K], h ⋆ a (x, y) ≜ f ⋆ (x, a) • ϕ ⋆ (x, y) K a ′ =1 f ⋆ (x, a ′ ) + (1 -f ⋆ (x, a))(1 -ϕ ⋆ (x, y)) K - K a ′ =1 f ⋆ (x, a ′ ).(2)Then we have• r(x, a) = ϕ ⋆ (x, y) ≥ 1{h ⋆ a (x, y) ≥ θ α } for all a ∈ [K]; • r(x, a) = ϕ ⋆ (x, y) = 1{h ⋆ a (x, y) ≥ θ α } for a = π ⋆ (x).Proof. Note that since ϕ ⋆ (x, y) ∈ {0, 1}, only one term can be non-zero in Eq. ( 2). If h ⋆ a (x, y) ≥ θ α , where θ and α are defined in Assumption 3, then the reward ϕ ⋆ (x, y) has to be 1 since otherwise, we have ϕ ⋆ (x, y) = 0 andθ α ≤ h ⋆ a (x, y) = 1 -f ⋆ (x, a) K - K a ′ =1 f ⋆ (x, a ′ ) ≤ 1 K -α < θ α ,where the second and the third inequality are due to Assumption 3. This leads to a contradiction. Therefore, we know that the realized reward is 1 if h ⋆ a (x, y) is no less than θ α . Therefore, 1{h ⋆ a (x, y) ≥ θ α } can be viewed as an underestimator of r(x, a). To prove the second property, consider the case in which a = π ⋆ (x). Then, we know that when ϕ ⋆ (x, y) = 1, we must also haveh ⋆ a (x, y) ≥ θ α since h ⋆ a (x, y) = f ⋆ (x, π ⋆ (x)) K i=1 f ⋆ (x, a) ≥ f ⋆ (x, π ⋆ (x)) α ≥ θ α ,where the first inequality uses the first property in Assumption 3 and the second inequality uses the second property in Assumption 3.Lemma 2 shows that the function h ⋆ (x, y) defined in Eq. ( 2) satisfies two important properties. First, 1{h ⋆ a (x, y) ≥ θ α } serves as a reward underestimator for all the policies. Second, it matches the reward of the optimal policy. Note that this is different from [Maghakian et al., 2022, Eq.(3) ], since they only consider the deterministic binary reward for each context-action pair, and they do not show that the constructed reward estimator matches the reward of the optimal policy.Based on these two properties, we know that if we have access to h ⋆ , then the policy π that maximizes the surrogate reward E 1{h ⋆ π(x) (x, y)} ≥ θ α also maximizes the true expected reward.Next, we show how to learn this h ⋆ via uniformly collected samples. Define the function class H as:H = h : X × Y → ∆ K , h a (x, y) = f (x, a)ϕ(x, y) K i=1 f (x, i) + (1 -f (x, a))(1 -ϕ(x, y)) K - K i=1 f (x, i) f ∈ F, ϕ ∈ Φ, a ∈ [K] .Note that |H| = |F| • |Φ|. Since h ⋆ models the posterior distribution over actions when the learner selects her action uniformly randomly, we collect N tuples of (x t , a t , y t ) by sampling a t uniformly from [K] and find the empirical risk minimizer (ERM) h ∈ H over these samples using squared loss.In the following lemma, we show that h enjoys O log |H| N excess risk with high probability.Lemma 3. Let {(x i , a i , y i )} N i=1 be N i.i.d. samples where x i ∈ D, a ∈ π Unif , and y i is the corresponding feedback. Let h be the ERM with respect to the squared loss defined as follows:h = argmin h∈H N i=1 ∥h(x i , y i ) -e ai ∥ 2 2 .(3)Then, with probability at least 1 -δ, we haveEQUATIONEQUATIONThe full proof is deferred to Appendix A. Different from the classic one-dimensional squared loss, here we consider the ℓ 2 -loss between two vectors in ∆ K . Directly applying the generalization bound for each entry leads to a K-factor worse bound. Instead, our proof is based on the observation that the loss function ∥h(x, y) -e a ∥ 2 2 , when seen as a function of h, satisfies the so-called strong 1-central condition [Van Erven et al., 2015, Definition 7] . Moreover, these results can be extended to function classes with infinite size and bounded covering number based on Theorem 7.7 of [Van Erven et al., 2015] .Now we show how to construct a reward estimator based on the ERM h. According to Section 3.1.1, an intuitive form of the reward (under)estimator is 1{ h a (x, y) ≥ θ α }. However, since the indicator function is not Lipschitz, 1{ h a (x, y) ≥ θ α } can be very different from 1{h ⋆ a (x, y) ≥ θ α } even with the generalization bound proven in Lemma 3. To resolve this issue, we propose a Lipschitz variant of the indicator function (defined in Eq. ( 6)) and show that it also satisfies the two properties shown in Lemma 2. Lemma 4. Define G(v, β, σ) asEQUATIONThen, for any context x ∈ X , action a ∈ [K], and feedback y ∈ Y generated via context x and the realized reward r(x, a), we have the following two properties with σ ≜ 12 θ α -1 K-α > 0.Algorithm 1 Off-Policy IGL Input: number of exploration samples N , parameters α, θ and σ = 12 θ α -1 K-α . for t = 1, 2, • • • , 2N doReceive context x t , sample a t ∼ π Unif , and observe signal y t . Calculate the empirical risk minimizer h as in Eq. ( 3). Construct the reward decoder r σ (x, y, a) = G( h a (x, y), θ α -σ, σ) where G is defined in Eq. ( 6).Calculate π = argmax π∈Π 2N i=N +1 π(a i |x i ) • r σ (x i , y i , a i ) where Π = {π f : f ∈ F}. for t = 2N + 1, . . . , T do Execute policy π. • r(x, a) = ϕ ⋆ (x, y) ≥ G(h ⋆ a (x, y), θ α -σ, σ), • r(x, a) = ϕ ⋆ (x, y) = G(h ⋆ a (x, y), θ α -σ, σ) if a = π ⋆ (x),The proof shares a similar spirit to Lemma 2 and is deferred to Appendix A. Notably, the functionG(v, β, σ) is 1 σ -Lipschitz in v,which is important in order to show concentration between the reward estimator with respect to the true posterior distribution G(h ⋆ a (x, y), θ α -σ, σ) and that constructed via the ERM function h: G( h a (x, y), θ α -σ, σ). In the following, we will show how to use the reward estimator G( h a (x, y), θ α -σ, σ) to design algorithms with provable guarantees.Built on the reward estimator in Section 3.1, we present our off-policy algorithm, summarized in Algorithm 1. Our algorithm follows the explore-then-exploit idea and consists of two phases. In the exploration phase, we perform uniform exploration and collect the dataset {x i , a i , y i } 2N i=1 . The first N samples are used to learn the reward estimator r and the rest N samples are used to learn the policy π with r. For the exploitation phase, we employ the learned policy π in the remaining T -2N iterations. We present the regret bound of Algorithm 1 in the following theorem.Theorem 1. Under Assumptions 1-3, Algorithm 1 with N = T 2/3 K 2/3 σ -2/3 log 1/3 (|H|T ) guaran- tees that Reg CB ≤ O T 2/3 K 2/3 σ -2/3 log 1/3 (|H|T ) .We remark that this is the first provably efficient algorithm for IGL with personalized reward. The key of the proof is to show that the learned policy π is near-optimal under the true reward. This is achieved by using the properties of function G in Lemma 4 and proving that the reward decoder r σ is close to the ground-truth. The full proof is deferred to Appendix B. Besides the dependence on T , K and log |H|, our regret bound also depends on σ -1 , which measures how sparse the reward vector is and characterizes the difficulty of the problem. For example, σ -1 = O(1) in the multi-class classification problem and σ -1 ≤ O(s 2 ) in the s-multi-label classification problem.Since on-policy algorithms are more favorable in practice, we further introduce an on-policy algorithm based on the inverse-gap weighting strategy. Following [Foster and Rakhlin, 2020] , we assume access to an online regression oracle AlgSq: at each round t ∈ [T ], the oracle AlgSq produces an estimator f t in the convex hull of F, then receives a context-action-reward tuple (x t , a t , r t ). The squared loss of the oracle for this round is defined as ( f t (x t , a t ) -r t ) 2 , which is on average assumed to be close to that of the best predictor in F.Assumption 4 (Bounded squared loss regret). For any sequence {(x t , a t , r t )} T t=1 , the regression oracle AlgSq guarantees the following regret bound for some Reg Sq that depends on T , K, and F:T t=1 f t (x t , a t ) -r t 2 -inf f ∈F T t=1 (f (x t , a t ) -r t ) 2 ≤ Reg Sq .Algorithm 2 On-policy IGL Input: online regression oracle AlgSq, number of exploration samples N , parameters α, θ, γ and , a ̸ = a,σ = 1 2 θ α -1 K-α . for t = 1, 2, • • • , N do Receive context x t ,EQUATIONwhere a = argmax a∈[K] f t (x t , a). Sample a t from p t and receive feedback y t . Feed (x t , a t , G( h at (x t , y t ), θ α -σ, σ)) to the oracle AlgSq where G is defined in Eq. ( 6).Based on the ground-truth inverse kinematics function h ⋆ , we define a functionf ⋆ (x, a) := E y|x,a G(h ⋆ a (x, y), θ α -σ, σ), which is always a lower bound on f ⋆ (x, a) according to Lemma 4. Since we only feed the surrogate reward to the oracle, we make another mild assumption that our regression function class F also realizes f ⋆ .Assumption 5 (Lower Bound Realizability). We also assume that f ⋆ ∈ F, where f ⋆ is defined asf ⋆ (x, a) = E y|x,a G(h ⋆ a (x, y), θ α -σ, σ)We now summarize our algorithm in Algorithm 2. After obtaining the inverse kinematics predictor h in the same manner as Algorithm 1, instead of uniform exploring, we use the estimated reward from the oracle and an inverse-gap weighting strategy [Abe and Long, 1999, Foster and Rakhlin, 2020] defined in Eq. ( 7). Different from the contextual bandit problem where the true reward is given and fed to the oracle, we feed the predicted reward G( h at (x t , y t ), θ α -σ, σ) to the oracle. One might wonder how such misspecification in rewards would affect the regret bound. Our key observation is that since we use the uniform policy to collect data used to train h, the generalization error of h is small for any a due to good coverage of the dataset on each action. Based on this observation, we prove the following theorem for Algorithm 2. Theorem 2. Under Assumptions 1-5, Algorithm 2 with certain choice of N and γ guarantees thatReg CB = O KT Reg Sq + σ -2/3 (KT ) 2/3 log 1/3 (|H|T ) .The proof mainly relies on the generalization bounds in Lemma 3 and the property of G in Lemma 4, and is deferred to Appendix C. We observe that Algorithm 2 enjoys the same dependence on T , K, σ -1 as Algorithm 1. For finite F, we can use Vovk's aggregation algorithm [Vovk, 1995] as the regression oracle and achieve Reg Sq = O (log |F|), making the second term in the regret bound negligible. 3 While in theory our on-policy algorithm does not seem to be more favorable than the off-policy algorithm (mostly because they both need to uniformly explore for a certain period in order to build h), it can still perform better in practice, as shown in our experiments. 
experiments: 
 In this section, we apply IGL to learning from image feedback and learning from text feedback. Specifically, we conduct experiments on the MNIST dataset and a conversational dataset to verify the effectiveness of our algorithms and the Lipschitz reward estimator constructed by Eq. ( 6). We use PyTorch framework [Paszke et al., 2019] and parameter-free optimizers [Orabona and Tommasi, 2017] to learn the reward estimator and the policy. For both algorithms, we set the number of exploration samples N = 5000 and pick the parameter σ ∈ {0, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3} andθ α ∈ { 1 3 + σ 2 , 1 2 + σ 2 }.For the on-policy algorithm, we use a time-varying exploration parameter γ t = √ Kt as suggested by Foster and Krishnamurthy [2021] . We run the experiments on one NVIDIA GeForce RTX 2080 Ti.The interaction lasts for T = 60000 rounds. We use two metrics to evaluate the performance of the algorithm, including the average progressive reward during the interaction process and the test accuracy on a held-out test set containing 10000 samples. When evaluating the on-policy algorithm on the test set, we take actions greedily according to f T . Since we use the uniform policy to collect data for learning the reward estimator, the progressive reward at that phase is counted as 1 K .We run the experiments with 4 different random seeds and report the mean value and standard deviation in Table 1 . The running averaged reward over the entire T rounds are shown in Figure 1 . We can see that both algorithms achieve good performance, despite never observing any true labels. While the theoretical regret guarantees for both algorithms are of the same order, empirically, the on-policy Algorithm 2 performs better than Algorithm 1 with over 90% test accuracy. This is because the on-policy algorithm uses the inverse-gap weighting strategy to achieve a better trade-off between exploration and exploitation, while the off-policy algorithm learns the policy from uniform exploration. On the other hand, to demonstrate the effectiveness of the Lipschitz reward estimator, we compare the performances of the Lipschitz estimator Eq. ( 6) with a binary reward estimator r binary (x, y, a) = 1{ h a (x, y) ≥ θ α }, where the parameter θ α is searched over the same space. The results in Table 1 show that the Lipschitz reward estimator improves over the binary one by a clear margin for both algorithms. This matches our theoretical analysis that highlights the vital role of the Lipschitzness of the reward estimator in obtaining good regret guarantees. We also plot the performance of Algorithm 2 under both true reward and constructed reward in the left figure of Figure 2 . 4 The figure shows that the constructed reward is indeed a lower bound of the true reward, and the policy can learn from the constructed reward effectively.We further consider an application of learning with text feedback. The IGL framework fits this problem well since this is a natural reward-free setting involving learning from user's text feedback, which is idiosyncratically related to the quality of the actions taken and the question asked. Specifically, given the input of a question, the learner needs to select one of the K possible answers. Instead of Figure 1 : Running averaged reward of Algorithm 1 and Algorithm 2 on MNIST. Note that Algorithm 1 uniformly explores in the first 2N = 10000 rounds, and thus its averaged reward at t = 10000 is about 1/K = 0.1. receiving whether the selected answer is correct, the learner only receives user's text feedback to the chosen answer. The goal of the learner is to choose the best answer only based on such text feedback.Dataset Construction Our dataset is constructed as follows. Specifically, we construct our question set S = {q i } i∈ [20000] from Chatbot Arena datasets [Zheng et al., 2024] . Then, for each question q i ∈ S we ask a larger language model G with a high ELO score on the chatsys leaderboard [Chiang et al., 2024] to generate a "good" answer g i,0 with r i,0 = 1; and ask a (much) smaller language model B with a (much) lower ELO score to generate 4 "bad" answers b i,j with reward r i,j = 0, j ∈ {1, 2, 3, 4}. Specifically, we pick G to be "Qwen1.5-32B-Chat" with ELO score 1134 and B to be "Qwen1.5-0.5B-Chat" with ELO score 5 less than 804 [Bai et al., 2023] . 6 For each questionanswer tuple (q i , g i,0 , b i,1 , b i,2 , b i,3 , b i,4 ), we ask another large language model R to simulate a user response f i,j , j ∈ {0, 1, 2, 3, 4} to the good (bad) answers under the instruction that the user is satisfied (unsatisfied) with the answer. We pick R to be Qwen1.5-32B-Chat as well. This forms our final dataset S Conv = {(q i , (g i,0 , f i,0 , r i,0 ), {(b i,j , f i,j , r i,j )} j∈[4] )} i∈ [20000] . Again, the true reward is never revealed to the learner, and we only use this reward to measure the performance of our algorithm. The prompt we use is deferred to Appendix D.1. We generate our dataset using one A100 GPU for two weeks.Given the superior performance of Algorithm 2 over Algorithm 1 on the MNIST dataset shown in Section 4.1, we only test Algorithm 2 on the conversational dataset. We use the first N = 10000 data points to learn h and the remaining |S| -N = 10000 data points to learn the optimal policy based on the reward function constructed via h. We use the same parameter-free optimizer as the one in Section 4.1. Next, we introduce the construction of h and the regression oracle:Inverse kinematic model. The model class H we consider is the pretrained language model Llama-3-8B-Instruct [AI@Meta, 2024] with an additional multi-class classification head. 7 The language model is prompted with a question-answer-feedback tuple (x, a, y); see Appendix D.2 for the prompt. To learn the inverse kinematic model, we use parameter efficient fine-tuning [Mangrulkar et al., 2024] with a rank-1 LORA adapter [Hu et al., 2021] and binary cross entropy loss, which is with respect to the indicator of whether-or-not the predicted action corresponds to the action selected in the tuple. 5 The bad model B is not displayed on the leaderboard; 804 is the lowest displayed score. 6 "Qwen1.5-32B-Chat" is available at https://huggingface.co/Qwen/Qwen1.5-32B-Chat and "Qwen1.5-0.5B-Chat" is available at https://huggingface.co/Qwen/Qwen1.5-0.5B-Chat."Llama-3-8B-Instruct": https://huggingface.co/meta-llama/Meta-Llama-3-8B-Instruct. We successfully learn h using one A100 GPU within 6 hours. After obtaining h, we construct the reward estimator G( h a (x, y), θ α -σ, σ) with σ = 0.1, α = K 2 = 5 2 , and θ = 1.Regression oracle. Similar to the inverse kinematic model, the reward prediction function class F is again based on the pretrained Llama-3-8B-Instruct model but with an additional regression head. Specifically, the language model is prompted only with a question-answer pair (x, a) using the prompt deferred to Appendix D.3 and predicts a score in [0, 1] for this question-answer pair. The regression oracle again applies parameter efficient fine-tuning with a different rank-1 LORA adapter on the regression loss, which measures the error of predicting the output of the reward predictor G( h a (x, y), θ α -σ, σ). This process is done on one A100 GPU within 3 hours.Results. The empirical results on the conversational dataset are shown in Figure 2 . We show the running averaged true reward and the running average constructed reward received by Algorithm 2 after the first N = 10000 rounds of learning h. The x-axis is the time horizon and y-axis is the value of average reward. Similar to our experiment results in Section 4.1, the right figure in Figure 2 shows that our constructed reward estimator is a lower bound on the true reward, matching our theoretical results in Lemma 4, and Algorithm 2 is able to learn the reward effectively through the text feedback with the constructed reward estimator.A Proofs in Section 3.1Lemma 1. For any context x ∈ X , suppose that the learner picks a uniformly random action a ∈ [K].Let r and y be its realized reward and the corresponding feedback. Then, under Assumption 1 and Assumption 2, the posterior distribution of a given the context x and feedback y equals toEQUATIONwhere f ⋆ and ϕ ⋆ are the true expected reward and feedback decoder defined in Assumption 2.Proof.Pr[a|x, y] = Pr[a|x] • Pr[y|x, a] Pr[y|x] = Pr[a|x] Pr[r = 1|x, a] • Pr[y|x, a, r = 1] + Pr[r = 0|x, a] • Pr[y|x, a, r = 0] Pr[y|x] = Pr[a|x] f ⋆ (x, a) • Pr[y|x, r = 1] + (1 -f ⋆ (x, a)) • Pr[y|x, r = 0] Pr[y|x] = Pr[a|x] f ⋆ (x, a) • Pr[r = 1|x, y] Pr[r = 1|x] + Pr[a|x] (1 -f ⋆ (x, a)) • Pr[r = 0|x, y] Pr[r = 0|x] = Pr[a|x] f ⋆ (x, a) • Pr[r = 1|x, y] K a ′ =1 Pr[a ′ |x]Pr[r = 1|x, a ′ ] + Pr[a|x] (1 -f ⋆ (x, a)) • Pr[r = 0|x, y] K a ′ =1 Pr[a ′ |x]Pr[r = 0|x, a ′ ] = Pr[a|x] f ⋆ (x, a) • Pr[r = 1|x, y] K a ′ =1 Pr[a ′ |x]f ⋆ (x, a ′ ) + Pr[a|x] (1 -f ⋆ (x, a)) • Pr[r = 0|x, y] K a ′ =1 Pr[a ′ |x](1 -f ⋆ (x, a ′ ).Recall that π Unif = 1 K • 1 is the policy which uniformly samples an action regardless of the context. Under π Unif , we know thatPr[a|x, y] = f ⋆ (x, a) • ϕ ⋆ (x, y) K a ′ =1 f ⋆ (x, a ′ ) + (1 -f ⋆ (x, a))(1 -ϕ ⋆ (x, y)) K - K a ′ =1 f ⋆ (x, a ′ ).Lemma 3. Let {(x i , a i , y i )} N i=1 be N i.i.d. samples where x i ∈ D, a ∈ π Unif , and y i is the corresponding feedback. Let h be the ERM with respect to the squared loss defined as follows:h = argmin h∈H N i=1 ∥h(x i , y i ) -e ai ∥ 2 2 .(3)Then, with probability at least 1 -δ, we haveEQUATIONE x∼D,a ′ ∼πUnif,y|x,a ′ ∥ h(x, y) -h ⋆ (x, y)∥ 2 ≤ O   log |H| δ N   .(5)Proof. For notational convenience, we denote (x, y, a) by Z and define ℓ h (Z) = ∥h(x, y) -e a ∥ 2 2 . Now we aim to show that ℓ h (Z) satisfies the strong η-central condition for some η > 0 [Van Erven et al., 2015] . Specifically, we aim to show thatEQUATION)To show this, direct calculation shows thatE Z [exp(-η(ℓ h (Z) -ℓ h ⋆ (Z)))] = E x,y exp(-η∥h(x, y) -h ⋆ (x, y)∥ 2 2 ) • E a|x,y exp -2η(h(x, y) -h ⋆ (x, y)) ⊤ (h ⋆ (x, y) -e a ).Since E a|x,y [e a ] = h ⋆ (x, y), the random variable (h(x, y) -h ⋆ (x, y)) ⊤ (h ⋆ (x, y) -e a ) given x and y is zero-mean and is within the range [-2∥h(x, y) -h ⋆ (x, y)∥ 2 , 2∥h(x, y) -h ⋆ (x, y)∥ 2 ]. Therefore, we know that (h(x, y) -h ⋆ (x, y)) ⊤ (h ⋆ (x, y) -e a ) is ∥h(x, y) -h ⋆ (x, y)∥ 2 2 -sub-Gaussian and we haveE Z [exp(-η(ℓ h (Z) -ℓ h ⋆ (Z)))] ≤ E x,y exp(-η∥h(x, y) -h ⋆ (x, y)∥ 2 2 ) exp 4η 2 ∥h(x, y) -h ⋆ (x, y)∥ 2 2 2 = E x,y exp 2η 2 -η ∥h(x, y) -h ⋆ (x, y)∥ 2 2 .Picking η = 1 2 proves Eq. ( 8). Noticing the fact that |ℓ h (Z)| ≤ 4 for all h ∈ H and applying Theorem 7.6 in [Van Erven et al., 2015] proves Eq. ( 4). Now we prove Eq. ( 5). Noticing the fact that E a|x,y [e a ] = h ⋆ (x, y) and applying this to Eq. ( 4), we know that with probability at least 1 -δ,E x,y ∥ h(x, y) -h ⋆ (x, y)∥ 2 2 ≤ O log |H| δ N .This means thatEQUATIONFurther applying Jensen's inequality shows thatEQUATIONThen, for any context x ∈ X , action a ∈ [K], and feedback y ∈ Y generated via context x and the realized reward r(x, a), we have the following two properties with σ ≜ 12 θ α -1 K-α > 0. • r(x, a) = ϕ ⋆ (x, y) ≥ G(h ⋆ a (x, y), θ α -σ, σ), • r(x, a) = ϕ ⋆ (x, y) = G(h ⋆ a (x, y), θ α -σ, σ) if a = π ⋆ (x),Proof. To prove the first property, we showϕ ⋆ (x, y) = 1 if h ⋆ a (x, y) ≥ θ α -σ. Specifically, if h ⋆ a (x, y) ≥ θ α -σ and ϕ ⋆ (x, y) = 0, then we know that θ α -σ ≤ h ⋆ a (x, y) = 1 -f ⋆ (x, a) K - K i=1 f ⋆ (x, i) ≤ 1 K -α ,leading to a contradiction according to the definition of σ. Therefore, when h ⋆ a (x, y) ≥ θ α -σ, we haveϕ ⋆ (x, y) = 1, which is surely an upper bound of G(h ⋆ a (x, y), θ α -σ, σ) since G(h ⋆ a (x, y), θ α -σ, σ) ≤ 1. When h ⋆ a (x, y) < θ α -σ, by definition, we know that G(h ⋆ a (x, y), θ α -σ, σ) = 0 ≤ ϕ ⋆ (x, y).Combining the two cases finishes the proof for the first property.To prove the second property, note that when ϕ ⋆ (x, y) = 1 and a = π ⋆ (x), we haveh ⋆ π ⋆ (x) (x, y) = f ⋆ (x, π ⋆ (x)) K i=1 f ⋆ (x, i) ≥ θ α ,where the last inequality is by Assumption 3. This means that G(h ⋆ a (x, y), θ α -σ, σ) = 1 = ϕ ⋆ (x, y). When ϕ ⋆ (x, y) = 0, we haveh ⋆ π ⋆ (x) (x, y) = 1 -f ⋆ (x, π ⋆ (x)) K - K i=1 f ⋆ (x, i) ≤ 1 K -α ≤ θ α -σ, meaning that G(h ⋆ a (x, y), θ α -σ, σ) = 0.This finishes the proof.B Proofs in Section 3.2For any policy π and reward estimator r σ , we define the value function V (π, r σ ) and the empirical value function V (π, r σ ) as follows:EQUATIONEQUATIONwhere {(x i , a i , y i )} 2N i=N +1 is collected with the uniform policy π Unif . The true value function V (π) is defined as:V (π) = E x∼D K a=1 π(a|x) • f ⋆ (x, a) .Using Lemma 4, we can establish the equivalence between V (π ⋆ ) andEQUATIONIn the following lemma, we prove that π is near optimal under the true reward. Lemma 5. Under Assumption 2 and Assumption 3, the following holds with probability at least 1 -3δ:V (π ⋆ ) -V ( π) ≤ O   K σ log |H| δ N   ,where π is defined in Algorithm 1.Proof. We first introduce some high probability events that the following analysis is based on. First, according to Hoeffding's inequality together with a union bound over π ∈ Π (note that |Π| = |F| ≤ |H|), with probability at least 1 -δ, we have for any π ∈ ΠEQUATIONIn addition, according to Hoeffding's inequality with a union bound over h ∈ H, with probability at least 1 -δ, we have for any h ∈ H, the following inequality holds:EQUATIONCombining Eq. ( 14) with Eq. ( 5) in Lemma 3, we know that with probability at least 1 -2δ,EQUATIONThe following analysis is based on the condition that Eq. ( 13) and Eq. ( 15) hold.Bounding V (π, r σ ) -V (π, r ⋆ σ ). We first show that for any policy π ∈ Π, the prediction from r σ is close to r ⋆ σ in terms of the empirical value function defined in Eq. ( 10), whereEQUATIONThe third inequality is because G(v, β, σ) is 1 σ -Lipschitz in v and the last inequality is from Eq. ( 15).Lower bound V (π) by V (π, r σ ). Then, we show that for any policy π ∈ Π, V (π) is lower bounded by V (π, r σ ):EQUATIONThe first inequality is from Lemma 4 and the second inequality is from Eq. ( 13) and Eq. ( 16). Recall that π = max π∈Π V (π, r σ ), we then know that with probability at least 1 -3δ, 16))EQUATION)) ≤ V (π ⋆ ) -V (π ⋆ , r σ ) + O   K σ log |H| δ N   (optimality of π on V (π, r σ )) ≤ V (π ⋆ ) -V (π ⋆ , r ⋆ σ ) + O   K σ log |H| δ N   (Eq. (EQUATION( 12))which finishes the proof.Next, we prove Theorem 1.Theorem 1. Under Assumptions 1-3, Algorithm 1 with N = T 2/3 K 2/3 σ -2/3 log 1/3 (|H|T ) guarantees that Reg CB ≤ O T 2/3 K 2/3 σ -2/3 log 1/3 (|H|T ) .Proof. We bound Reg CB as follows:Reg CB = E T t=1 f ⋆ (x t , π ⋆ (x t )) - T t=1 f ⋆ (x t , a t ) ≤ 2N + E T t=2N +1 f ⋆ (x t , π ⋆ (x t )) - T t=2N +1 f ⋆ (x t , a t ) = 2N + E T t=2N +1 f ⋆ (x t , π ⋆ (x t )) - T t=2N +1 f ⋆ (x t , π(x t )) ≤ 2N + T • E [V (π ⋆ ) -V ( π)] ≤ O N + T K σ log(|H|T ) N .The last step is from Lemma 5 with δ = 1 T . Picking N = T 2/3 K 2/3 σ -2/3 log 1/3 (|H|T ) finishes the proof.C Proofs in Section 3.3 Theorem 2. Under Assumptions 1-5, Algorithm 2 with certain choice of N and γ guarantees that Reg CB = O KT Reg Sq + σ -2/3 (KT ) 2/3 log 1/3 (|H|T ) .Proof. According to Eq. ( 9), we know that with probability at least 1 -δ,EQUATIONwhere the last inequality uses Eq. ( 9). Let a ⋆ t = argmax a f ⋆ (x t , a) and recall that f ⋆ (x, a) := E y|x,a G(h ⋆ a (x, y), θ α -σ, σ) ∈ F. We haveEQUATIONThe last step is from Foster and Rakhlin [2020, Lemma 3] . Recall that r σ (x t , y t , a t ) = G( h at (x t , y t ), θ α -σ, σ). Direct calculation shows thatEQUATION)where the last step is by AM-GM inequality. For the second term, we know thatEQUATIONwhere the first inequality is from Jensen's inequality; the third inequality is from that G(v, β, σ) is 1 σ -Lipschitz in v; and the last inequality is by Eq. ( 18) with δ = 1 T . Combining Eqs. ( 19)-( 21), we obtain thatReg CB ≤ O γReg Sq + T Kγ log(|H|T ) σ 2 N + T K γ + N .Picking N = 1 σ T Kγ log(|H|T ) and γ = min KT /Reg Sq , σ -2/3 (KT ) 2/3 log -1/3 (|H|T ) , we obtain thatReg CB ≤ O KT Reg Sq + σ -2/3 (KT ) 2/3 log 1/3 (|H|T ) ,which finishes the proof.The prompt we use in answer generation basically the question itself shown as follows. We replace "question" by x in our experiment.The prompt we use in feedback generation as follows. We replace "question" and "answer" by x and a respectively in our experiments. We replace "mood" by "satisfied" ("not satisfied") when the answer is generated by Qwen1.5-32B-Chat (Qwen1.5-0.5B-Chat).System: You are a user simulator. A user has been presented a Question and an Answer. Simulate the user's next statement. The user is {mood} with the Answer to the Question. Question: {question} Answer:{answer}The prompt we use in learning the inverse kinematic model is as follows. We replace "question", "answer", and "feedback" by x, a, and y respectively in our experiments.System: You are a conversation evaluating agent. The prompt we use in learning the reward predictor is as follows. We replace "question" and "answer" by x and a respectively in our experiments. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This work is mostly theoretical, and we do not foresee any negative ethical or societal outcomes. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We properly cite the used dataset and models and respect the licenses.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.We point out that the idea behindXie et al. [2022] cannot be used in our setting where feedback can be dependent on the context. Specifically,Xie et al. [2022] propose an algorithm which learns the value function and the reward decoder separately for each action. Generalizing their idea to our setting would then mean learning the value function and the reward decoder for each context, which is infeasible since there could be infinitely many contexts.We refer readers toFoster and Rakhlin [2020] for more examples of regression oracles when F is not finite.Both the true reward and the constructed reward values are averaged over the rounds after the first N rounds of uniform exploration. 
 
 Appendix:  


Decision: All the reviewers have a positive feedback on this paper concerning IGL. It seems that the authors received several bits of constructive feedback in the discussion phase, much of which can be easily incorporated through discussion of the setting, results and better contextualization of their technical challenges and accomplishments. I encourage the authors to address these concerns.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: Same as weakness.
paper_summary: 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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: No potential negative social impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: (-) 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: 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?
limitations: limitations: No "Limitations" section is provided in the paper.

Comments: title: Follow-up Response
comment: Thank you for your further clarification, which does help better understand the context. Please ensure to address the original concerns and incorporate the feedback in revision. The clear explanations will enhance the clarity of the current draft. 

Considering the responses from authors during rebuttal, I raise my score accordingly.
Thanks for your further questions. We emphasize that the idea behind the algorithm design of Xie et al., [2022] **cannot** be used in our setting. Specifically, Xie et al., [2022] consider the setting where the feedback is independent of the context given the reward and the action, so they learn the value function $f_a$ and the reward decoder $\psi_a$ separately for each action $a\in[K]$. Generalizing their idea to our setting would then mean learning the value function and the reward decoder **for each context**, which is infeasible since there could be infinitely many contexts. Therefore, we have to propose a new method, that is, constructing a reward decoder via inverse kinematic, for our setting.
I thank the authors for their detailed response.

To further clarify,  Xie et al. [2022] studies the setting of $(y|a, r)$, the current draft studies the setting of $(y|x, r)$. Could you elaborate more on why the studied setting may not borrow the techniques from Xie et al. [2022]? More specifically, what are the main technical differences when dealing with feedback depending on context and reward v.s. feedback depending on action and reward?
Thanks for your suggestion. We will incorporate this into the next version. If our response addresses your concern, please do consider re-evaluating our paper.
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}\}$.