Provably Efficient Interactive-Grounded Learning with Personalized Reward
Authors: Mengxiao Zhang
Yuheng Zhang
Haipeng Luo
Paul Mineiro
Venue: NeurIPS 2024 poster (2024)
Keywords: Online learning
Interactive-Grounded Learning
Contextual Bandit
Primary area: bandits

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.

Provably Efficient Interaction-Grounded Learning with Personalized Reward
Mengxiao Zhang University of Iowa mengxiao-zhanggen zhang@uiowa, edu
Yuheng Zhang University of Illinois Urbana- Urbana-Champiia Champaign yuhengz201llinois edu
Haipeng Luo University of Southern Califomna haipengl@use @usc.llusc..ccc
Paul Mineiro
Microsoft Research
mnineirromiicoooff..oo
Abstract
Eeeraction-Groundee Learning (IGL) [Xie et al., 2021] is a powerful framework which 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 ubiquitous in applications such 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 simite-sample effects. Our solution 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-frre free settings that arise in practice. Experimental results showcase the importance of using our Lipschitz reward estimator and the overall effectiveness of our algorithms.
Introduction
Traditional bandit problems [Auer al., 2002] 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 diffieult to obtain in many real-world scenarios, including human-computee interface applications [Pantic and Rothkrantz, 2003, Freeman et al., 2017] and recommender systems [Yi et al., 2014, Wu al., 2017]. Recently, Xie al. [2021] study new Learning (IGL), where the learner interacts with the environment
setting called Interaction-Grounde 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 information-theoreti perspective, IGL is intractable unless further assumptions 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 unrealistic in many scenarios. For example, different users interact with recommender systems in different ways even under the same latent reward [Maghakian al., 2022]. This inspires to study IGL with personalized rewards, setting where the feedback depends on the context. Although
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 dnteractiongrroundee 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 1. we first propose a novel reward estimator via inverse kinematics. Specifically, using the samples collected by applying uniform policy, we construct 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(T 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 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.
1.1 Related Work
Interaction-Grounde 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 is independent of context conditioned on both the action and the reward. 2 Hu et al. [2024] follows approach to enforce
version, where the feedback
the same setting Xie et al. [2021] but proposes an information-theore 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 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, 201 8, 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 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.
2 Preliminary
Problem setup. Throughout the paper, we use [N] to denote the set (1, N) for positive integer N. The problem of online Grruaddee-rruudee 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 E [T'. the environment reveals a stochastic context Dt E X' i.i.d. drawn from an unknown distribution D, and the learner decides action a E [K] from 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(z,, 02) E {0, 1), she receives feedback y/ )
"We point out that the idea behind Xie et al. [2022] cannot be used in our setting where feedback can be dependent on the context. Specifically, Xie [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.

---

Feedback dependence assumption. We follow the assumption proposed in [Maghakian et al., 2022] that the feedback conditionally independent of the action given the context and the realized reward.
For arbitrary (a, (1,a,T;3) tuple where the reward and the feedback y are generated based on the context and action we assume y is conditionally independent of action given context and reward r. In other words, we assume that y T,
Assumption 1.
As mentioned, compared to prior work [Xie et al., 2021, 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 classes F C [X'[ [0, 1)) and & S (X' y + {0, 13). where F characterizes the mean of the reward for given context- action pair, and Φ characterizes the realized reward given the context and the received feedback. policy π X + A(K) specifies the action probability conditioned on the context. For each I E F. we use f to denote the induced policy which takes action greedily according to f. that is, [y(aax) = 1 {a- = argmax,'e|kt f(x, d')}, Va [K]. We also use the shorthand n² for the optimal policy r. 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 function f E F such that E[r(xe, a)( I (xx,,) for all E [K] and E [T]. Furthermore, there exists a feedback decoder o² E O such that (It, Me) = r(2,, ar) for all t E [T].
For simplicity, we also assume that F and & are finite with cardinality [F] and |o]. Our results can be further generalized to broader function classes, which will discussed in later sections.
Identifiability. As mentioned in [Xie et al., 2021, 2022, Maghakian et al., 2022], it impossible to learn if we do not break the symmetry between reward being and being Following [Maghakian et al., 2022], we make the following assumption:
Assumption 3 (Identifiability). For any X, I defined in Assumption 2 satisfies that: I) K ft S a for some 0 < a 2 max f*(x,, a) where K K-a-
a
The first condition says that the sum of the expected reward over actions less than 3/2 given any context v. That is to say, the reward vector is sparse if f", a) E {0, 1). The second condition says that for each context æ E 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 a = s and
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:
T
Reges = E
Σ (a, (x.)
E
(2,, ax)
Other notations. We denote the (K d)-dimensian simplex by Ax. - Let 1 be the all-one vector in appropriate dimension and Tuait k Ak. For d-dimensional vector Rd, denote its i-th entry by v, 1(-} is the indicator function and e, is the i-th standard basis vector in an appropriate dimension.
3 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 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-then- exploit and the second one based on inverse-gap gap weighting (IGW).
3

---

3.1 Reward Estimator Construction via Uniform Exploration
We first show how we construct reward estimator based on feedback collected from a uniform policy, which serves as the most important component in our two algorithms.
3.1.1 Inverse Kinematies
When the reward for each context- -cttxtnnatiinnnoo pair deterministic and binary, Maghakian 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, (2) well, and we include here for completeness.
Lemma 1. For any context x E X, suppose that the learner picks a uniformly random action [K]. Let r and be its realized reward and the corresponding feedback. Then, under Assumption I and Assumption 2, the posterior distribution of given the context x and feedback y equals to
Pr(a|z, vl (x, 60) (x,
K 1 (z) (x,
ΣK (traa)
where f* and o² are the true expected reward and feedback decoder defined in Assumption 2.
Now we show how to infer the true reward from this inverse kinematies. Specifically, we show:
Lemma 2. For any context a E X' and action a E [K], let r(z, a) be the realized reward and be the feedback. Let h (x, y) E AK be such that for each
[K].
hr (2 y) (a a) 6 (2,1)
(1 (1- (* a)) 0' (x,1))
(2)
Em=1 (I,
K- 2 - (I(
Then we have
r(z,0) (I, (1 2 for
for all [K]:
r(z,0) = o² (x. = (1,((,)))) 2 ) for = (
Proof. Note that since (<x, v) E {0. 1}. only one term can be non-zero in Eq. (2). If hg > 0 where and a are defined in Assumption 3, then the reward (xx y) has to be 1 since otherwise, we have o² (z, 0 and
0 < (M
1- (x,
1
0
K 1- <
K K-a
where the second and the third inequality are due to Assumption 3. This leads a contradic- tion. Therefore, we know that the realized reward is 1 if (2r is less than Therefore, 1(h; (x, 3) 2 _ can be viewed as an underestimator of r(x, a). To prove the second property, consider the case in which x (rr). Then, we know that when di (2, = 1, we must also have he (x, y) 2 0 since
(x)x (()T
0 a a
(x, v)
KK (t,
where the first inequality uses the first property in Assumption and the second inequality uses the second property in Assumption 3.
Lemma 2 shows that the function ht (x, y) defined Eq. (2) satisfies two important properties. First,
[h: (xr,y) y) 2 2 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 (T,
also maximizes the true expected reward.
3.1.2 Learning the Posterior Distribution via ERM
Next, we show how to learn this ht via uniformly collected samples. Define the function class H as:
H = h: x' Ax. ha (2, = f(x, a)),a))(z.)) + (1 - f(x, a) o(x,8))
K- E ((x, E
REF,DEO.aeE
Note that [H] = |F| | Since ht models the posterior distribution over actions when the learner selects her action uniformly randomly, we collect N tuples of (æe, (t y1) by sampling 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 HH excess risk with high probability.
Lemma 3. Let {x, 0gs ve) 5- be N iii.d. samples where x, E D, E Uiitt and ys is the corresponding feedback. Let h be the ERM with respect to the squared loss defined as follows:
h argmin WCH
[|M v)) ea:112
Then, with probability at least
8, we have
log H
Ez m.m.D..muuaall...
-al (1,(,))) - -call3 0
(4)
N
log [H
[[ -tt (z.v))la
5o
(5)
N
The full proof deferred to Appendix A. Different from the classic one-dimensional squared loss, here consider the f2-loss between two vectors in Ax. Directly applying the generalization bound for each entry leads to a K -factor worse bound. Instead, our proof based on the observation that loss function ||A(,, 3) eall 112. when seen 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].
3.1.3 Constructing Lipschitz Reward Estimators Based on h
Now show how construct a reward estimator based the ERM h. According Section 3.1.1, an intuitive form the reward (under)estimatori is (2, y) Z ). However, since the indicator function is not Lipschitz, (Na (x. y) 2 )) can be very different from 1 (hr y) 2 0 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,8, as
Glv,8,0 = 1 (V- -
< +1 +o].
(6)
Then, for any context x E X, action a E [K], and feedback y E y generated via context x and the realized reward r(x, a), we have the following two properties with 2 x-a) >0
5

---

Algorithm 1 Off-Policy IGL
Input: number of exploration samples N, parameters a, and o = 2 K-n
for 1 1, 2, ..... 2.N do
| Receive context Tt, sample ~ minit and observe signal yt-
Calculate the empirical risk minimizer h as in Eq. (3). Construct the reward decoder For (zz v.a) = G(ha (2, 0, where G' defined in Eq. (6).
Calculate î argmax
Eie L (aa Fo (T (1,, where IT { : F).
for t 2N + ......T do Execute policy
0( (I. G(ha(1 (2, v). o,0).
r(,,0) o (x, G( v) o, if=
The proof shares similar spirit to Lemma 2 and is deferred to Appendix A. Notably, the function G(u, 3, a) is -Lipsschitz in u, which important in order to show concentration between the reward estimator with respect to the true posterior distribution G(h,(2r, y). @ -a, a) and that constructed via the ERM function h: ((,a(z,)) y). e estimator (1,
a o, O). the following, we will show how use the reward o, σ) to design algorithms with provable guarantees.
3.2 Off-Policy Algorithm
Built the reward estimator in Section 3.1, we present off-policy algorithm, summarized in Algorithm 1. Our algorithm follows the ppllor-theen-exlooii idea and consists of two phases. In the exploration phase, we perform uniform exploration and collect the dataset { di, yi J The first N samples are used to learn the reward estimator and the rest N samples are used to learn the policy स with F. For the exploitation phase, employ the learned policy मे in the remaining T -2N iterations. We present the regret bound of Algorithm in the following theorem.
Theorem 1. Under Assumptions 1-3, Algorithm with 22/3 22/3 2/3 log 1/3 1/3 (HHT) guaran- tees that Regcs S 5O (1223 (2233 2/3 // ((H(TT
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 f. 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, o = O(1) in the multi-class classification problem and o -1 s (s²2) in the s-multi-labe classification problem.
3.3 On-Policy Algorithm
Since on-policy algorithms are more favorable in practice, we further introduce an on on-policy algorithm based on the inverse-gap weighting strategy. Following [Foster and Rakhlin, 2020], assume access to an online regression oracle AlgSq: at each round t E [T], the oracle AlgSq produces an estimator fo in the convex hull of F. then receives context-action- reward tuple (I,, ag,aarr rt). The squared loss of the oracle for this round is defined as (fr a.) r2 which is average assumed to be close to that of the best predictor in F.
Assumption 4 (Bounded squared loss regret). For any sequence {(I,, or re) TE the regression oracle Aq guarantees the following regret bound for some Regsa that depends on T, K, and F:
T
T (f(2,, at) 10--r) rz)²² Regsa
inf SEF
Σ

---

Algorithm 2 On-policy IGL
Input: online regression oracle AlgSq, number of exploration samples N, parameters a, 0, and
K-o
for 1 1,2..... do
| Receive context sample az muiif and observe signal y/-
Calculate the empirical risk minimizer h as in Eq. (3).
for = N + +l.... do
Receive context
Obtain estimator S. from the oracle AlgSq.
Calculate the action distribution Pt as
a a a (+ (((2))))))
Pt.a
Ea'zaPor Pa',
= ā
where â = ae fe( a). Sample ae from pt and receive feedback yr.
Feed (Iz, de, Ghaa, (ot, y1), 8 o, o, to the oracle AlgSq where G' is defined in Eq. (6).
Based on the ground-truth inverse kinematics function h*, we define a function f( EyJa,a [G (z. y), o, o)], which is always lower bound on fa a) according Lemma Since we only feed the surrogate reward to the oracle, we make another mild assumption that our regression function class also realizes f*
Assumption 5 (Lower Bound Realizability). We also assume that f E where f*r is defined as [" a) Eylz, [G(Ma v), 2 a, a,
We now summarize our algorithm in Algorithm 2. After obtaining the inverse kinematics predictor h in the same manner as Algorithm I, instead of uniform exploring, we use the estimated reward from the oracle and 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(ho, (Ie, Ve), o, o) 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 collect data used to train h, the generalization error of is small for any 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, Algorithmn 2 with certain choice of N and guarantees that Reges = O (VKTRegsq + -2/3 log ((1(T))
The proof mainly relies on the generalization bounds Lemma and the property of G in Lemma 4, and is deferred to Appendix C. We observe that Algorithm 2 enjoys the same dependence T, K, For finite F, we can use Vovk's aggregation algorithm [Vovk, 1995] as the
-- as Algorithm regression oracle and achieve Regsa O (log [F]), making the second term the regret bound negligible.3 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 f),, can still perform better in practice, as shown in 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 refer readers to Foster and Rakhlin [2020] for examples of regression oracles when J is not finite.
7

---

Table 1: Performance of Algorithm and Algorithm 2 on the MNIST dataset.
Algorithm
Reward Estimator
Average Progressive Reward
Test Accuracy
Binary Lipschitz
0.614 (0.012)
72.6% (1.5%)
Off-policy Algorithm
0.638 (0.042)
75.9% (4.9%)
Binary Lipschitz
0.718 (0.006)
89.4% (4.0%)
On-policy Algorithm 2
0.740 (0.022)
90.3% (3.7%)
4.1 Experiments on Learning from Image Feedback
Experiment Setup We first conduct experiments on MNIST dataset and implement both the off- policy algorithm Algorithm 1 and the on on-policy algorithm Algorithm 2. The setup is as follows: each step the learner receives an image 24 with ground-truth label I, and picks action o, from {0, (0.....000 ,9) as the predicted label. If the prediction is correct, the learner receives as feedback an image y/ with digit (1, + 1) mod 10; otherwise, the learner receives an image with digit (4, - 1) mod 10. Therefore, different from the experimental setup in [Xie et al., 2021], our feedback y/8 does depend on both the context and the reward. Both function classes H and F are implemented as two-layer convolutional neural networks.
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
5000 and pick the parameter o E {0, 0.05, 0.1, 0.15,. 0.2, 0.25, 0.3) and E ( + - 3 ). For the on-policy algorithm, we use a time-varying exploration parameter Tt. = VKl 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 fr. Since we use the uniform policy to collect data for learning the reward estimator, the progressive reward that phase is counted K.
Results 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 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 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, compare the performances of the Lipschitz estimator Eq. (6) with binary reward estimator Dinaryy (ar, y, a) 1 17ha (z. y) > _). where the parameter 2 is searched over the same space. The results in Table 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. The figure shows that the constructed reward is indeed lower bound of the true reward, and the policy can learn from the constructed reward effectively.
4.2 Experiments on Learning From Text Feedback
We further consider an application of learning with text feedback. The IGI. framework fits this prob- lem 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
Both the true reward and the constructed reward values are averaged over the rounds after the first N rounds of uniform exploration.
8

---

0.7
0.6
Average Reward
0.5
0.4
0.3
0.2
Algorithm 2
Algorithm 1
0.1
10000
20000
30000 40000 50000 60000 Iterations
Figure I: Running averaged reward of Algorithm and Algorithm 2 on MNIST. Note that Algo- rithm uniformly explores in the first 2NN 10000 rounds, and thus its averaged reward at 10000 is about 1/K = 0.1.
receiving whether the selected answer is correct, the learner only receives user's text feedback to 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 S {qe he (2000]] from Chatbot Arena datasets [Zheng et al., 2024]. Then, for each question E S we ask a larger language model G with a high ELO score on the chatsys leaderboard [Chiang generate "good" answer 91,0 with Ts,u
and ask (much) smaller language model B with (much) lower ELO score to generate 4 "bad" answers bigj with reward ri.j = 0, j E 21, 3, 4). Specifically, we pick G to be "Qwen (Qwen1.5-32B, 1-5-32B-hhat" with EL.O score 1134 and to be "Qwenl .5-0.5B-Chaf* with ELO score less than 804 [Bai et al., 2023].6 For each question- answer tuple (ge, 91.0. b bi,,, 3 by,4), we ask another large language model R. to simulate user response fi.s- j {0, 1, 2, 3, 4] to the good (bad) answers under the instruction that the user is as well. This forms our J (20000] Again, the true reward
al., 2024]
satisfied (unsatisfied) with the answer. We pick R to be Qwenl.5-322--C.
final dataset Scony {gg (gr,,, fio, ri.o), [brij fi.j (igirri)))ee never revealed to the learner, and we only use this reward to measure the performance of our algorithm. The prompt use is deferred to Appendix D.1. We generate our dataset using one A100 GPU for two weeks.
4.2.1 Algorithm Configurations and Results
Given the superior performance of Algorithm over Algorithm I 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 learn Te 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 l 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 additional multi-class classification head." The language model is prompted with a question-anseee wwwwer-feedbeeteeeeee
tuple (æz, a, y); see Appendix D.2 for the prompt. To learn the inverse kinematic model, use parameter efficient fine-tuning [Mangrulkar al., 2024] with rank-1 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.
'The bad model B is not displayed on the leaderboard; 804 is the lowest displayed score. "'Qwenl5 5.5-3BB-Chii "Qwenl.5-0.. S..eel.5-0..B--o "hat"" is available at http:s///uggggggtcccoo////////// http:/gghh..aat.eooooe/o///eeaaa
available https://huuginngfcce co wttp:/aaaacccccee/eeeeeeeee/ee/e htt////eee///reiiieeeeeeee 5-32B- Chat and Chat.
TH "Lamma-3.a 3-8B Instrrcct"" https: http:://hgggnngace.ccmmm ct htap:///h//oo////nn//////o/e//ee -Lama- Instruct.

---

0.80
0.75
Aver Peraage Reward
Average Reward
0.7
0.70
0.6
0.5
(unobserved) rewards
True (unobserved) rewards Constructed rewards
Constructed
0.3
10000
20000
30000
40000
50000
10000
12000
14000 16000 18000 20000
Iterations
Iterationn
Figure 2:
Performance of Algorithm 2 under true (unobserved) rewards and constructed rewards. Left figure: Results on MNIST dataset after the first N uniform exploration rounds. Right figure: Results on our conversational dataset.
We successfully learn using one A100 GPU within hours. After obtaining h, we construct the K 2
reward estimator Ga, v), _ σ) with o = 0.1, a
and 0 =.
Regression oracle. Similar to the inverse kinematic model, the reward prediction function class F is again based the pretrained Llama-3-8B-Instruuct model but with additional regression head. Specifically. the language model is prompted only with a question-ansee answer pair (æ, a) using the prompt deferred to Appendix D.3 and predicts score in [0, 1] for this question-answer pair. The regression oracle again applies parameter efficient fine-tuming with a different rank- I LORA adapter on the regression loss, which measures the error of predicting the output of the reward predictor G(aa (x. - o. or. This process is done on one A100 GPU within hours.
Results. The empirical results on the conversational dataset are shown in Figure We show the running averaged true reward and the running average constructed reward received by Algorithm after the first N 10000 rounds of learning h. The æ-axis is the time horizon and y-axis is the value of average reward. Similar to our experiment results Section 4.1, the right figure in Figure 2 shows that constructed reward estimator is lower bound the true reward, matching theoretical results in Lemma 4, and Algorithm 2 is able to learn the reward effectively through the text feedback with the constructed reward estimator.
Acknowledgments and Disclosure of Funding
HL and MZ were supported by NSF Award 114-1943607.
References
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pages 1. Citeseer, 1999.
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1666 1646. PMLR. 2014.
Al@Metta Llama 3 model card. 2024. URL httpp//p//ggthhaa..oo//o/o////ea MOtn/MODDEL_AADD md.
Peter Auer, Nicolo Cesa- Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256 2002.
10

---

Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang. Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li. Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chenggiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang. Shijie Wang. Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang. Hao Yang, Jian Yang, Shusheng Yang. Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu. Qwen technical report. arXiv preprint MXXv:2339.16609 2023.
Gábor Bartók and Csaba Szepesvári. Partial monitoring with side information. In International Conference on Algorithmic Learning Theory, pages 305-319. Springer, 2012.
Joeran Beel, Stefan Langer, Andreas Nürnberger, and Marcel Genzmehr. The impact of demographies (age and gender) and other chercctaaatsssssscc on evaluating recommender systems. Research and Advanced Technology for Digital Libraries: International Conference on Theory and Practice of Digital Libraries, TPDL 2013, Valletta, Malta, September 22-26, 2013. Proceedings 3, pages 396-400. Springer, 2013.
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E Gonzalez, al. Chatbot arena: An open platform for evaluating Iims by human preference. arXiv preprint MXXiv:2403.041333 2024.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning. pages 1539-1548. PMLR, 2018.
Dylan Foster and Akshay Krishnamurthy, Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. Advances Neural Information Processing Systems, 31, 2018
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
Euan Freeman, Graham Wilson, Dong-Bach Vo, Alex Ng, Ioannis Politis, and Stephen Brewster. Multimodal feedback in hci: haptics, non-speech audio, and their applications. In The Handbook of Baatiimodal-Muliisnnnan Interfaces: Foundations, User Modeling, and Common Modality Combinations- Volume 1, pages 277-317.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.099 09685, 2021.
Xiaoyan Hu, Farzan Farnia, and Ho-fung Leung. An information theoretic approach to interaction- grounded learning. arXiv preprint 2rXiv:2401.05015 2024.
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Proceedings of Thirty Third Conference on Learning Theory, pages 2328- 2369, 2020.
John Langford and Tong Zhang. The epoch- mroch-greddy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Jessica Maghakian, Paul Mineiro, Kishan Panaganti, Mark Rucker, Akanksha Saran, and Cheng Tan. Personalized reward learning with antraactiongroondde learning (igl). arXiv preprint arXiv:2211.15823, 2022.
Mangrulkar, Gugger, I.. Debut, Y. Belkada, and Paul S. Peft: State-of-the-art parameter-effiient fine-tuning methods. https://giiii /ttp:////ttt////// com/huugiinfface/pttt 2024. Accessed: 2024-05-14 14.
11

---

Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. Advances in Neural Information Processing Systems, 30, 2017. URL https: //github. hoom//rmmen79//aa paramtterrre...
Maja Pantic and Leon JM Rothkrantz. Toward an affect-sensitive multimodal human-computer interaction. Proceedings of the IEEE, 91(9):1370-1390 2003.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Donghee Shin. How do users interact with algorithm recommender systems? the interaction of users, algorithms, and performance. Computers in human behavior, 109:106344, 2020.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Tim Van Erven, Peter Grunwald, Nishant Mehta, Mark Reid, Robert Williamson, et al. Fast rates in statistical and online learning. Journal of Machine Learning Research, 54(6). 2015.
Vladimir G Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
Qingyun Wu, Hongning Wang, Liangjie Hong, and Yue Shi. Returning is believing: Optimizing long- term user engagement in recommender systems. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 1927-1936, 2017.
Tengyang Xie. John Langford, Paul Mineiro, and Ida Momennejad. Interaction-groundee learning. In International Conference on Machine Learnnng, pages 1114--11423 PMLR, 2021.
Tengyang Xie, Akanksha Saran, Dylan Foster, Lekan Molu, Ida Momennejad, Nan Jiang, Paul Mineiro, and John Langford. interaction-goounder learning with action-inclusive feedback. Ad- vances in Neural Information Processing Systems, 15:12529-12541 2022.
Xing Yi, Liangjie Hong, Erheng Zhong, Nanthan Nan Liu, and Suju Rajan. Beyond clicks: dwell time for personalization. In Proceedings of the Sth ACM Conference on Recommender systems, pages 113-120, 2014.
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo, and Paul Mineiro. Efficient contextual bandits with uninformed feedback graphs. International Conference on Machine Learning, 2024a.
Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Minciro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems, 36, 2024b.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li. Eric Xing, et al. Judging ilm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36, 2024.
12

---

A Proofs in Section 3.1
Lemma 1. For any context E X, suppose that the learner picks uniformly random action [K]. Let r and be its realized reward and the corresponding feedback. Then, under Assumption I and Assumption 2, the posterior distribution of given the context x and feedback y equals to
Pr(a|x,y] v) f* a) (I.y)
(1 (L-
K E
where f* and of are the true expected reward and feedback decoder defined in Assumption 2.
Proof.
Pr[a|æ]
Pr[y|æ,
Pr(ala,
Pr[y[æ]
Prfr 12 Prfvla, a, 1] Pr(r = 0/2, a) Pr|vlæ,,,r 0]
Pr[a|a]
Pr[y[æ]
f* a) Pr(y|æ,r + (x a)) Pr(u/x, 0]
Pr[a|a]]
Pr[y|ar
/ (x, a) Pr(r = 1|x .l
(1 (1 a)) Pr(r = 0/r,,/)
Pr[a|a]]
+ Pr[a/22]
Pr(r 1|x]
Pr[r = 0|
f (x. a) Pr(r Pr|r=11a0 1/2, vl
(1 f (z. a)) Pr(r = 0| vl
Pr[a|ax]
Pr(a|a)
De== Pr|a||=]Pr(r-1111 1/
Ed'=1 Pr|a/|=]|Pr[- = 0|z, a'
f" a) Prrr 1/2,8]
(x, Pr(r = 0/z, yl
= -r[[|
+ Pr[a|
Σx= Pr(al|=]f((z,aa')
K Σø= Pr[a' [x][ f1,
Recall that Tunit = _ 1 is the policy which uniformly samples an action regardless of the context. Under Uniff we know that
f*1x,)) (x, E stx,aa) K - (x
(1- -1 (x,
Pr(ala,
Lemma 3. Let (zi, ai v)) be N i.i.d samples where I; E D, E TUnis and ys is the corresponding feedback. Let h be the ERM with respect to the squared loss defined as follows:
h argmin WCH
Σ |1 v.) ea,
(3)
Then, with probability at least we have
[2 log 3
Dan.Danrmaaaul... [1(2,v) ea 112111000,0) -cal2] 5
(4)
log [
EawD a's [1ī((1,)) h (z. (x,
0
(5)
N
Proof. For notational convenience, we denote (x, y, a) by and define (Z) = [1 y) - 6 13
Now aim to show that (Z) satisfies the strong 77centaal condition for some 1) > 0 [Van Erven et al., 2015]. Specifically, we aim to show that
Ez (exp(-n(Ex(Z) 4n (2))) <
(8)
To show this, direct calculation shows that Ez (exp(-n((x(Z) Ex- (2)))]
13

---

Bryy [exp(- -n/hh(z v) - h (x,, v) Bata. [exp (-2n(h(z,)) (. v)) 1 (h' (I, --a)]]]]]]]]]
Since Balz.y [ex] 10" (x, y). the random variable (rx
ea) given a and
y is zero-mean and is within the range -
(., (22.,))l21 Therefore.
know that (h(x, v) h" (x, v)) (x, c.) is (1( h (2, ( and
have
Eg (exp( - (()(())))))))))))))))))()) - 2 (2)))
4nf1[h(z, y) - h² (z. 2 ]
S Eny exp(-nill(( 3) ht (z, 1) exp
2
E [exp ((2n² - 7) |1,(z, y) h (z. v) [ž]]
Picking 7 = proves Eq. (8). Noticing the fact that (2) < for E H and applying
Theorem 7.6 in [Van Erven et al., 2015] proves Eq. (4).
Now we prove Eq. (5). Noticing the fact that Eala,yleal = h" (z, 3) and applying this to Eq. (4), know that with probability at least 1 1 6,
[ log N
Ex,y [1((z,)) - 12" -1',, so
(o(t,,)-h"'
5
This means that
log H
Enw Ea' Taa Eyl [1 M) 1²" (x,
Further applying Jensen's inequality shows that
Ex~DBa' wom Bulla [[M(2,)) htt (2,
ELwDEEa' Eylz,a' (Vlhta,ww 1- (x.
Be Byleear [ w) - (, vx1
(Jensen's inequality)
[7d] log N
O
o
Lemma 4, Define G(v, 0), as
Glv, ((v,B,o) = 1
1(v 3
(6)
Then, for any context x E X, action a E [K], and feedback y E y generated via context x and the
realized reward rlz.oz a), we have the following two properties with 2 1 ( xtaa > O.
r(z,0) 60 (x, (z v) o,0),
r(z,0) = (x y) = G( v). - afa
Proof. To prove the first property, we show of (xx 3) ht y) 2 e o. Specifically, h y) 2 8 a and oz (z, y) = O. then we know that
0
1- (z,))
1
K K- (x,
K-a (x,,)
14

---

leading to a contradiction according to the definition of a. Therefore, when (z, 2 8 -0, . we have
6 (2r, y) 1, which is surely upper bound of (a,a(a y), - since G(h (x, y) -0,0) S When (z, y) _ o, by definition, we know that G( y), af 0,0) I o² (z.
& Combining the two cases finishes the proof for the first property.
To prove the second property, note that when @ (5, 1 and a x* (x), have
1 (a) (2, v) (2, T
0
2
f
a''
where the last inequality is by Assumption 3. This means that G (z y), - -000) = == (x.z))
When o (xx 3) = O, we have
h (z. 1- --, 1 K - 0.
EZ M(,,
meaning that (( v), a 0,0) = This finishes the proof.
B Proofs in Section 3.2
For any policy x and reward estimator ro, we define the value function (TT,Ta) and the empirical value function (r) follows:
2N
(IT,To)= N
Σ
K ((akk))) (o Wes a.),
(10)
N+1
((T,To) EgwDD ga [K <(aaz) ro (x, y,
(11)
where {(x, at, N=1 collected with the uniform policy Tnnif. The true value function V(x) is defined as:
K mala)) 8 (x,,
V(T) B
Σ
Using Lemma 4, we can establish the equivalence between ((TT) and V(=*,, r3) where (2, G(b (a, v), at 0, o. V(=*)
BedDaami Rame [K xx f" a)]
= EE a www.wa
[K (ala) (I,
(Assumption 2)
K . (alx) G (1 0 0, 0,0
= -B H.w.Damaaalll a.
(Lemma 4)
= =V(n", rd))
(12)
In the following lemma, 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 36:
K
7 log
S O
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 's inequality together with union bound over E IT (note that
| [H]), with probability at least 1 - 8, we have for any π E IT
H log
- -
5
(13)
N
15

---

In addition, according to Hoeffding's 's inequality with union bound over E H, with probability at least 1 8, we have for any h E H. the following inequality holds:
2N
Σ
|1((as,
ht (2x, ye) Eg maa [11b(x, y) h- (x, 122
N+1
log
H &
(14)
Combining Eq. (14) with Eq. (5) in Lemma 3, we know that with probability at least 26,
2N
2N
Σ
(2,, 81) - ha, (I vi) -
1
[haas wi) - 12" Mi)ll2
N t= N+1
N
i=N+1
V
log
[H|
so
(15)
The following analysis is based on the condition that Eq. (13) and Eq. (15) hold.
Bounding Fo) - rz) We first show that for any policy E II, the prediction from Po close r in terms of the empirical value function defined in Eq. (10), where ior y, & G(h (z, v), o,
2N
(T. ((TTrr))
S
1
Σ
K (aa(2;)) Fo 0i) - (xi. vi)
N
N=++1
2N
K
Σ
(2,, Bi. a:) - r- (2
N
i=++
K
0 -0,0) G(hi (2ii, (1), yi), 0 G(ha, (2i, vk)s (xi,
N
N=++1
2N
K
Pa (I4,, N1) N2 (wrs, mti
No
N=++1
K
2N
| vi) h² (x1,
No
K
log
o
(16)
N
The third inequality is because G(v, 3, o) Lipischhitz in and the last inequality is from Eq. (15).
Lower bound V(T) by fa). Then, we show that for any policy E II, V(T) is lower bounded by f.r
V(T)= = ELND
Σ x(al))
Exp commuur (K<(al))
E E Parntur Byiz (T(az))
(Assumption 2)
(n -
0,0)
Enn D Eylza
16

---

((T,ra) ((T, VVT rz) -
(Eq. (11)
H (T. fx,
2 (o) - o log N
(17)
The first inequality from Lemma and the second inequality from Eq. (13) and Eq. (16). Recall that मे = maX (mt Fo), we then know that with probability at least 1 - 36,
K
log
((=))-((3)) s V(E,))
5
(Eq. (17))
N
[H]
K
log
<V(**) - ((=",
(optimality of क on (T,
K
log
<V(+T) - (( +
(Eq. (16)
N
log [H
K
I <V(T)) - (T
(Eq. (13))
N
K
log H 5
0
(Eq. (12))
N
which finishes the proof.
Next, we prove Theorem
Theorem Under Assumptions 1-3, Algorithm with N 22/3 2/3 log ((H(() guaran-
tees that Regcs S (12/3/2f3 2/3 1/3 ( (1H(TT).
Proof. We bound Regcs as follows:
Reges = E
Σ (Z,, (x+))
T Σ
$ 2N +E
Σ (anaa)
L
1=
T
2N +E
Σ (+
Σ
(((n((I))))
L
1=N
< 2N + +T P. [V( (T*) V(T)
50 N TK
log (H(T)
N
The last step is from Lemma 5 with 8 = #. Picking N = 2/13 -2/3 log ((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 ry guarantees that
Regcs O (VKTRegs, + 223 (KT))22) 2/3 log2/3((HH (1H1T)).
17

---

Proof. According to Eq. (9), we know that with probability at least - 6,
k
Σ
Ex DEyDay
(ho(2,)) v) 11 (2, 31)
o=1
(Ro(2, - (1 8) 2
< K Eyn Dar.Daan
K Byn aan
[10(2,, v) h- (2. v)
log
$ 0
(18)
N
where the last inequality uses Eq. (9). Let at argmax, (T,, a) and recall that f" a) =
Bylaa (2, o,0)] F. We have
T
Σ ((r)
Regce =
T Byleen 1o (Fr,, (1),,
E
at at 16 (Fe,
Σ
(From Assumption 2)
< E
Σ (2 at) Σ (I),
(From Lemma 4)
t=1
$ 2 E
Σ (felzr)) (1),
O TK
(19)
The last step is from Foster and Rakhlin [2020, Lemma 3]. Recall that F (Ie, Uc. ae)
G(ha, (Ie, vi), 0 a o, Direct calculation shows that
T Σ (t) Fo (21. az))² - - Fo at))
Rogsa 2
E
(f Σ (F((a)) az + (1 - 2F (11. Vl,
E
Σ (F(( (x))
T Σ (itlse - (21,, (x)) Egg (2 Me az)l
+ 2E
T
T (L' ot) Ey, (o Ve, at)))
2 E
Σ (flon - -
- 2E
(20)
where the last step is AM-GM inequality. For the second term, we know that
E
f (x)) By Fo (Ie, Vc, az)
E
Eyllzeoor [G h (Fee
ye),
0,00
G Ray (2,, ve).
0
o, )))
<
E
Ey la ( Na Ut),
0 0
G
(Fe,
0
o,
27
18

---

K
ho (2 v), 1 -0000)
8 haa (ha o, 0
27
G
Bylaria
a
K
(M((Te))) - (o( v) )
E
E Bylzr
t=1
o=1
TK Log((H/2)
0
(21)
o2N
where the first inequality is from Jensen's inequality; the third inequality is from that G(v, 8, is L-LLisschizz in and the last inequality is by Eq. (18) with = 7/1 Combining Eqs. (19)-(21), we obtain that
RegcB SO (oRRegsa +
TK* log (T()
TK
+ N.)
o2N
7
Picking = TK> log( H) and 7 min {v KT/Regss 0 2/3 2/3(K2)2 log 1/3 (1317))
obtain that
RegcB 0 (v KTRResa to -/33 lo0/////11/////// (030(K)))/10g)/ 2/
which finishes the proof.
D
Omitted Details in Section 4
Prompt Used in Generating Dataset D.1
The prompt we use in answer generation basically the question itself shown as follows. We replace "question" by in experiment.
Prompt
(question]
The prompt we use in feedback generation as follows. We replace "question" and "answer" by a and respectively in our experiments. We replace "mood" by "satisfied" ("not satisfied") when the answer is generated by Qwen I. 1.5-32B-Chat (Qwen1 --0.55--hht).
Prompt
System: You
simulator. A user has been presented Question and Answer. Simulate the user's next statement. The user is (mood) with the Answer to the Question. Question: [question] Answer: knswer:(answerr) (answer)
D.2 Prompt Used Learning Inverse Kinematic Model
The prompt we use in learning the inverse kinematic model is as follows. We replace "question", "answer". and "feedback" by æ, a, and respectively in our experiments.
Prompt
You are conversation evaluating agent. Given a User's Question, an Answer, and the User's Feedback: determine if the User's Feedback is consistent with Answer. Respond with Yes or No only.
System:
User's Question: (question)
Answer: (answer)
User's Feedback: feedback)
19

---

Respond with Yes or No only.
D.3 Prompt Used in Learning Policy
The prompt we in learning the reward predictor follows. We replace "question" and "answer" by x and respectively in our experiments.
Prompt
System:
You an Answer evaluating agent. Given User's Question and an Answer: assess if the Answer is good. Respond with Yes or No only.
User's Question: [question]
Answer: ( ]
Respond with Yes or No only.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See abstract and Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section and Section 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
See Assumption 1, Assumption 2, Assumption 3, Assumption 4, Assumption 5,
and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Algorithm 1, Algorithm 2, and detailed descriptions in Section and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Mibllic/guides/CdeSSbbmii inn for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. wwtpcc/cppwlcgggiicccoeeooo
/CodeSubmia agionolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 4.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurip:: http:////eerrss..cpplpc///e/iiie cttppp//////Ehhheeeceeeelllll
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics. The research con- ducted in this paper conforms with in every respect.
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 to preserve anonymity (e.g.. if there special consid- eration 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 particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "ovDTuA968m", "reviewer": "Reviewer_8SUA", "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. \n\nThe 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.", "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?  \n\nPaper is well written.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Provide T^{2/3} style of regret bounds for IGL setting with personalized rewards. \n\nMost of the assumptions and problem setting follow classical contextual bandits literature. \n\nExperimental 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. \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **“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 the learner has access to a class $\\Phi$ which contains a decoder $\\phi$ that maps the context and observation to actions. Thus this becomes close to Model-Based methods in RL, etc, and hence we can expect statistical traceability. Can the authors elaborate if there are any other differences?”**\n\nReply: Besides the differences mentioned by the reviewer, in the partial monitoring setting, in order to achieve sublinear regret guarantees, it is assumed that the difference between the loss of any two arms can be represented as a certain linear combination of the signal matrix. Comparing the assumptions in these two different problems, we think those in IGL might be easier to interpret in real applications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jUc3hZX8PI", "reviewer": "Reviewer_qSGo", "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.", "questions": "Same as weakness.\n\nQ1: It seems straightforward to apply explore-then-exploit and inverse-gap weighting. Could you please state the challenges encountered when proving the regret guarantees?\n\nQ2: 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": "Same as weakness.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n\nThe 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.\n\nIn Table 1, the difference between Binary and Lipschitz reward estimation seems insignificant, which raises doubts about the practical contribution of the new estimator.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **“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.”**\n\nReply: Realizability is a well-established assumption in the contextual bandit literature [Foster et al., 2018, Foster and Rakhlin, 2020], and can be satisfied by using a rich function class as the reward predictor such as deep neural networks. \n\nIdentifiability is a necessary assumption in IGL to break the symmetry between reward being 1 and being 0. As demonstrated by examples in [Xie et al. ,2022], learning in IGL is impossible without breaking the reward symmetry. As mentioned in Lines 107-108, our identifiability assumption is satisfied in many scenarios with sparse rewards, including classification problems and recommender systems where the user is primarily interested in a very small subset of items. \n\n\n> **“In Table 1, the difference between Binary and Lipschitz reward estimation seems insignificant, which raises doubts about the practical contribution of the new estimator.”**\n\nReply: To verify that the advantage of our Lipschitz reward estimator is indeed significant, we run additional experiments using the on-policy Algorithm 2 on MNIST with 20 different random seeds. The binary reward estimator achieves an average progressive reward of 0.711 (0.040) and a test accuracy of 88.5% (3.5%). In contrast, the Lipschitz reward estimator achieves an average progressive reward of 0.748 (0.025) and a test accuracy of 90.6% (3.4%).\n\nAccording to the two-sample t-test, our Lipschitz reward estimator outperforms the binary one with greater than 95% confidence in terms of both average progressive reward and test accuracy. These results demonstrate the practical significance and contribution of the new estimator.\n\n> **“It seems straightforward to apply explore-then-exploit and inverse-gap weighting. Could you please state the challenges encountered when proving the regret guarantees?”**\n\nReply: While explore-then-exploit and inverse-gap weighting are well-established techniques in contextual bandits where the learner has access to the true reward, applying these methods in the context of IGL, where the learner only receives certain indirect feedback, presents significant challenges. \n\nFirst, to develop a provable algorithm, it is necessary to design an effective reward predictor. The step-function estimator used by Maghakian et al. (2022) is one such example. However, our analysis indicates that this estimator does not lead to a regret guarantee. Instead, we propose a novel Lipschitz reward estimator, which is essential for proving the regret guarantees.\n\nAdditionally, unlike the widely used optimism principle in bandit problems, we apply a pessimism approach instead: our predicted reward is an underestimator of the true reward. This design is also crucial for obtaining the regret guarantee, whose analysis is nontrivial: it involves leveraging the Lipschitz property of our estimator to address the discrepancy between the predicted reward and the true reward. This differs from the misspecification analysis typically conducted in contextual bandits.\n\nTo sum up, our approach and the theoretical analysis address the unique challenges posed by the IGL problem and are innovative and nontrivial in our opinion.\n\n> **“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.”**\n\nReply: According to the lower bound in the contextual bandit problem, the best regret bound we can hope for in IGL is $O(\\sqrt{KT})$. However, as we stated before, IGL is substantially more difficult than contextual bandit, so whether $O(\\sqrt{T})$ regret is achievable remains an open question. Nevertheless, we emphasize that our work presents the first provably efficient algorithm with sublinear regret in the personalized reward setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tlsd6Kfj5I", "reviewer": "Reviewer_LmpU", "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.", "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.\n\n2. What is the intuition of $\\sigma$? \n\n3. 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": "No potential negative social impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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. \n\nThe 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,\n\n1. 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. \n\n2. 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.\n\n3. 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. \n\n4. Compared to Algorithm 1, the performance guarantee of Algorithm 2 relies on more restricted assumptions (Assumptions 1 - 5), which can be difficult to satisfied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Comparison with contextual bandits and POMDP**\n\nAs the reviewer already pointed out, in IGL one only observes indirect feedback about the reward, while in standard contextual bandits one observes the reward directly. This clearly makes IGL more challenging than contextual bandits — in fact, without further assumptions (like those we made), learning in IGL becomes impossible. So we do not understand why the reviewer thinks IGL is not technically more challenging. If what you mean is that all we need is to construct reward estimators using the feedback received, then we emphasize again that our Lipschitz reward estimator is novel, and the previous estimator proposed by Maghakian et al. (2022) does not lead to a regret guarantee.\n\nAlso, we emphasize that IGL is not a simplified version of POMDPs, and they present their own unique challenges. In POMDPs, although the latent state is unobservable, the reward of the chosen action is still revealed to the learner, which means that POMDP algorithms do not need to address the symmetry breaking problem that is central to IGL.\n> **The conditional independence assumption for actions**\n\nNote that [Xie et al., 2022] in fact considers the conditional independence assumption for context, while we follow [Maghakian et al. (2022)] that considers the conditional independence assumption for actions. The two main reasons we study this setting are:. First, we believe that it does capture many real-world applications. For instance, in recommender systems, while different users may communicate their feedback differently, a given user typically expresses (dis)satisfaction in a consistent way. Thus, this is a realistic setting where the feedback depends only on the context (the user) and the reward (degree of satisfaction), but not the actual action (the recommended item).\n\nSecond, this seemingly restricted setting is already challenging enough, and there are no efficient algorithms with sublinear regret before our work. Thus, we believe that solving this challenge (which we did) is itself a significant contribution. Furthermore, our empirical results also validate the practicality and the effectiveness of our approach.\n\nWe do recognize the limit of our setting as pointed out by the reviewer though, and we leave the more general setting as an important future direction.\n> **“Require more advanced exploration strategies. Optimality of the provided bound.”**\n\nNote that in addition to the simple explore-then-exploit idea used in Algorithm 1, we also use the more sophisticated online exploration idea from Foster and Rakhlin [2020] in Algorithm 2. While we are not able to prove a better regret bound (mainly due to the fact that for learning $\\hat{h}$, we still use uniform exploration), Algorithm 2 does perform better than Algorithm 1 empirically, as shown in our experiments.\n\nWe are not certain about the optimality of our $O(T^{2/3})$ regret bounds. An obvious regret lower bound is $\\Omega(\\sqrt{KT})$ (from contextual bandits). Given that IGL is significantly more challenging (and also that $T^{2/3}$ is the optimal regret for a class of partial monitoring problems as mentioned by Reviewer 8SUA), it is possible that $T^{2/3}$ regret is indeed optimal in our setting.\n> **“Compared to Algorithm 1, Algorithm 2 relies on more assumptions”**\n\nWe would like to clarify that Algorithm 2 only relies on two additional assumptions, Assumptions 4 and 5, both of which are commonly used in the contextual bandit literature and reasonable in practice.\n\nAssumption 4 assumes that the square loss regret of the online oracle is bounded. As stated in line 240, we can use Vovk’s aggregation algorithm to achieve logarithmic regret for finite $\\mathcal{F}$. Additionally, as noted in footnote 1, there are many examples of regression oracles when $\\mathcal{F}$ is not finite, and we refer the reviewer to Foster and Rakhlin [2020] for further details.\n\nAssumption 5 assumes that our function class realizes one specific function $\\underline{f}^\\star$. This is similar to the widely used realizability assumption and can be satisfied with a rich function class such as deep neural networks.\n> **“Why a reward underestimator?”**\n\nIndeed, in many bandit problems, optimism is a commonly used exploration strategy. The fact that we need pessimism instead highlights the difference between IGL and standard contextual bandits. From a technical viewpoint, the reason we make sure that the predicted rewards are underestimators and at the same time pretty accurate for the optimal policy (Lemma 4) is that it then allows us to upper bound the regret under the true reward by the regret under the predicted reward (which the algorithm tries to minimize).\n> **“Intuition of $\\sigma$?”**\n\nIntuitively, $\\sigma$ characterizes the difference of function $h^\\star_{\\pi^\\star(x)}(x,y)$ when $\\phi(x,y)=0$ and $\\phi(x,y)=1$. As discussed in line 145-154, when $\\phi(x,y)=0$, we have $h^\\star_{\\pi^\\star(x)}(x,y)\\leq \\frac{1}{K-\\alpha}$ and when $\\phi(x,y)=1$, we have $h^\\star_{\\pi^\\star(x)}(x,y)\\geq \\frac{\\theta}{\\alpha}$. $\\sigma$ is then set to be half of this gap when constructing our reward estimator that is $1/\\sigma$-Lipschitz.\n> **“why algorithm 2 outperforms algorithm 1? Do they converge to similar performance? Regret plots are suggested.”**\n\nAlthough Algorithm 2 has the same $T^{2/3}$ regret bound as Algorithm 1, as stated in line 243, this is primarily because both need to uniformly explore in the first phase. However, in the second phase, Algorithm 2 is on-policy and employs the inverse-gap weighting strategy, which typically offers better exploration than the explore-then-exploit approach used in Algorithm 1. This is the main reason why Algorithm 2 empirically performs better, regardless how long the time horizon is. To further illustrate this, we have provided the average progressive reward plots in the rebuttal PDF, which indeed demonstrates that Algorithm 2 consistently outperforms Algorithm 1 over time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m0xbxFSYBP", "reviewer": "Reviewer_TjTV", "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.", "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.\n2. 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": "No \"Limitations\" section is provided in the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "(+) This is the first work to provide provably efficient algorithms with regret guarantees for IGL with personalized reward.\n\n(+) 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).\n\n(-) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **“The paper does not compare the proposed algorithms to the IGL-P algorithm proposed in (Maghakian et al., 2022).”**\n\nReply: We followed the reviewer’s suggestion and tested the algorithm of Maghakian et al. on the MNIST dataset. We found that it achieves less than 0.2 average progressive reward, significantly worse than our algorithms. We will add this result to our paper in the next version.\n\nBeside the issue of using step-function estimators, another main reason for this huge performance difference is that IGL-P trains the reward predictor (inverse kinematics part) in an online manner. Specifically, in each iteration, IGL-P updates the predictor using only the current sample, without reusing past samples for training. In contrast, our algorithms first employ uniform policies to collect a dataset and then train the predictor on this dataset for multiple epochs via supervised learning. Since the actions in our dataset are uniformly distributed, the dataset has good coverage for each action, ensuring better generalization performance for our predictor.\n\n> **“While there are justifications in the paper for using the Lipschitz reward estimators (Lemma 4), it is unclear why using $\\mathbb{1}\\lbrace\\hat h_a(x,y)\\ge\\frac{\\theta}{\\alpha}\\rbrace$ or the previous IGL-P algorithm could fail.”**\n\nReply: We do not have counter-examples showing that the binary reward function provably fails. However, from a technical perspective, Lipschitzness is crucial to control the difference between the empirical value function with respect to true rewards and that with respect to the estimated rewards (lines 486-487), and from an empirical perspective, we also show that our algorithm performs much better when equipped with our Lipschitz reward estimator compared to the binary one. \n\nTo further demonstrate the last point, we run additional experiments using the on-policy Algorithm 2 on MNIST with 20 different random seeds. The binary reward estimator achieves an average progressive reward of 0.711 (0.040) and a test accuracy of 88.5% (3.5%). In contrast, the Lipschitz reward estimator achieves an average progressive reward of 0.748 (0.025) and a test accuracy of 90.6% (3.4%). According to the two-sample t-test, the Lipschitz reward estimator outperforms the binary one with greater than 95% confidence in terms of both average progressive reward and test accuracy.\n\n> **“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?”**\n\nReply: We think prior knowledge on $\\alpha$ and $\\theta$ is usually easy to obtain in many setups. For example, as we mentioned after Assumption 3, in the s-multi-label classification problem (with $1\\leq  s < K/2$), we have $\\alpha = s$ and $\\theta = 1$. \n\nThe parameter $\\gamma$ controls the amount of exploration in the inverse-gap weighting (IGW) rule. Intuitively, smaller $\\gamma$ leads to more exploration among the actions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their detailed and valuable comments. To further illustrate that Algorithm 2 outperforms Algorithm 1, as suggested by Reviewer LmpU, we include the average progressive reward plot in the rebuttal PDF, which indeed demonstrates that Algorithm 2 consistently outperforms Algorithm 1 over time.

Meta-review: 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.
Decision: Accept (poster)