Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation
Authors: Long-Fei Li
Yu-Jie Zhang
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: MNL function approximation
regret analysis
reinforcement learning
Markov decision process
Primary area: reinforcement_learning

Abstract: We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. Despite its significant benefits, incorporating the non-linear function raises substantial challenges in both *statistical* and *computational* efficiency. The best-known result of Hwang and Oh [2023] has achieved an $\widetilde{\mathcal{O}}(\kappa^{-1}dH^2\sqrt{K})$ regret upper bound, where $\kappa$ is a problem-dependent quantity, $d$ is the feature dimension, $H$ is the episode length, and $K$ is the number of episodes. However, we observe that $\kappa^{-1}$ exhibits polynomial dependence on the number of reachable states, which can be as large as the state space size in the worst case and thus undermines the motivation for function approximation. Additionally, their method requires storing all historical data and the time complexity scales linearly with the episode count, which is computationally expensive. In this work, we propose a statistically efficient algorithm that achieves a regret of $\widetilde{\mathcal{O}}(dH^2\sqrt{K} + \kappa^{-1}d^2H^2)$, eliminating the dependence on $\kappa^{-1}$ in the dominant term for the first time. We then address the computational challenges by introducing an enhanced algorithm that achieves the same regret guarantee but with only constant cost. Finally, we establish the first lower bound for this problem, justifying the optimality of our results in $d$ and $K$.

Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation
Li Yu-Jie Zhang", Peng Zhao 1.2, Zhi-Hua Zhou 1.2
National Key Laboratory for Novel Software Technology, Nanjing University, China 2 School of Artificial Intelligence, Nanjing University, China 3 The University of Tokyo, Chiba, Japan
Abstract
We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. Despite its significant benefits, incorporating the non-linear function raises substantial challenges both statistical and computational efficiency. The best-known result Hwang and Oh [2023] has achieved an O / regret upper bound, where K is problem-dependen quantity, d is the feature dimension, H is the episode length, and K is the number of episodes. However, we observe that the number of reachable states, which
k- exhibits polynomial dependence can be as large as the state space size in the worst case and thus undermines the motivation for function approximation. Additionally, their method requires storing all historical data and the time complexity scales linearly with the episode count, which is computationally expensive. In this work, we propose a statistically efficient algorithm that achieves a regret of O(dH2 + k dd H²), eliminating the dependence on k- in the dominant term for the first time. We then address the computational challenges by introducing an enhanced algorithm that achieves the same regret guarantee but with only constant cost. Finally, we establish the first lower bound for this problem, justifying the optimality of our results in d and K.
Introduction
Reinforcement Learning (RL) with function approximation has achieved remarkable success in various applications involving large state and action spaces, such as games [Silver et al., 2016], algorithm discovery [Fawzi et al., 2022] and large language models [Ouyang et al., 2022]. Therefore, establishing the theoretical foundation for RL with function approximation of great importance. Recently, there have been many efforts devoted understanding the linear function approximation, yielding numerous valuable results [Yang and Wang. 2019, Jin et al., 2020, Ayoub et al., 2020].
While these studies make important steps toward understanding RL. with function approximation, there are still challenges to be solved. linear function approximation, transitions are assumed to be linear in feature mappings, such P(s"| a) ó(s' (,lss,o0 a) 0* for linear mixture MDPs and P(s a) = ø(s, a) T n² (=('') for linear MDPs. Here P(s'ls, )) is the probability from state to s' taking action a, ø(s' s, a) and d(s, a) are feature mappings, 6* and μ² (s') are unknown parameters. However, the transition function is probability distribution over states, meaning its values must lie Thus, the linearity assumption is restrictive and hard to satisfy in practice. An algorithm designed for linear MDPs could break down entirely if the underlying MDP is not linear [Jin et al., 2020]. While some works explore generalized linear [Wang et al., 2021] ] and general function approximation [Russo and Roy, 2013, Foster et al., 2021, Chen et al., 2023]. they focus on function approximation for value functions rather than transitions, hence do not tackle this challenge.
within [0. and sum
Correspondence: Peng Zhao <zhaop wwwe@allaaaaaaa.c.o.mm
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison between previous works and ours in terms of the regret and computational cost (including storage and time complexity). - Here K and x* are deeleeddeeeneent quantities defined in Assumption 1, d is the feature dimension, H is the episode length and K' is the number of episodes.
The computational cost per episode only highlight the dependence on the episode count k.
Reference
Regret
Storage
Time
MDP model
Hwang and Oh [2023]
O
((k)
((k)
homogeneous
UCRL-MNL-LL (Theorem 1)
((HH² + (
((k)
O(k)
inhomogeneous
UCRL-MNI-OL (Theorem 2)
Ö(dHAVK (HH2)
O(1) O(1)
inhomogeneous
Lower Bound (Corollary 1)
((dHVKK))
infinite action space
Towards addressing the limitation of linear function approximation, a new class of MDPs that utilizes multinomial logit function approximation has been proposed by Hwang and Oh [2023] recently. Such formula also aligns better with models like neural networks [LeCun et al., 2015], which inherently respect the probabilistic constraints through softmax layer and allow for greater expressive power. However, though it offers promising benefits, the introduction of non-linear functions introduces significant challenges in both statistical and computational efficiency. Specifically, the best-known approach of Hwang and Oh [2023] has achieved an "dH22 regret, where x is problem- dependent quantity that measures the effective non-linearity over the entire parameter space, d is the feature dimension, H is the episode length, and K is the number of episodes. Unfortunately, as we show in Claim 1, it holds that x > U², where U denotes the maximum number of reachable states, which equals to the size of the state space S in the worst case. This undermines the core motivation for function approximation, which aims to mitigate dependence on large state and action spaces. Furthermore, the method requires storing all historical data, and its time complexity per episode grows linearly with the episode count (i.e., (Kk at episode k). Thus, natural question arises:
possible to design both statistically and computationally efficient algorithms for RL with MNL functiioion approximation?
In this work, we answer this question affirmatively for the class of MNL mixture MDPs where the transition is parameterized by multinomial logit function. Our contributions are listed as follows:
For statistical efficiency, we propose the UCRL-MNI-LL algorithm, which attains a regret bound of Ö(H22 + x H²². Our result significantly improves upon the O(x- VV) rate of Hwang and Oh [2023], making the first time to achieve k-independent dominant term (note that the lower-order term still scales with x_ but does not depend on K, making acceptable). To achieve this, we propose tighter confidence set based on new Bernstein-type concentra- tion [Périvier and Goyal, 2022] instead of the standard Hoeffding-ty self-concordant-a like property [Bach, 2010] of the log-loss function to better use local information.
concentration, and exploit the
For computational efficiency, we propose the UCRL-MNL-OL algorithm, which enjoys the same regret bound as UCRL-MNI-LI, but with only constont storage and time complexity per episode. This is enabled by recognizing that the negative log- logllikeldoood function is exponentially concave, which motivates the use of online mirror descent with specifically tailored local norm [Zhang and Sugiyama, 2023] to replace the standard maximum likelihood estimation. Furthermore, we construct the optimistic value function by incorporating a closed-form bonus term through a second-order Taylor expansion, thus avoiding the need to solve a non-convex optimization problem.
We establish the first lower bound for MNL mixture MDPs by introducing a reduction to the logistic bandit problem. We prove problem-dependen dependent lower bound of ((dH / Kk²)) ) for infinite action setting, where x* an another groblem-dependen quantity that measures the effective non-lined loneeiiyyyyyyy over around the ground truth parameter. Though this does not constitute strict lower bound for
the finite action case studied in this work, it suggests that our result may be optimal in d and K.
Table provides a comparison between our work and previous studies, focusing on regret and computational costs, including both storage and time complexity.
After the submission of our work to arXiv [Li et al.. 2024a]. a follow up work by Park et al. [2024] proved a lower bound of 3/d113/2 VK) for the finite action setting. This confirms that our result is optimal in d and K.
2

---

Organization. We introduce the related work in Section 2 and present the setup in Section 3. Then, we design a statistically efficient algorithm in Section Next, we present an algorithm that achieves both statistical and computational efficiency in Section 5. Finally, we establish the lower bound in Section 6. Section concludes the paper. Due to space limits, we defer all proofs to the appendixes.
Notations. We use [0]]].]]] to denote min mainmmax(2.0 a),b) 6). For vector x E Fd and positive semi- definite matrix A Rdxdd denote ||x||A = vx Ax. For a strictly convex and continuously differentiable function ub : W + I,, the Bregman divergence is defined as D5 (W1, W2) = & (W1) & (W2) <V (W2). Wi - w2). We use the notation
(-) to indicate different types of dependencies depending on the context. For regret analysis, (-)) omits only constant factors. For computational costs, we use (-) to solely highlight the dependence on the number of episode as this is the primary
factor influencing the complexity. Additionally, we employ ())) to hide all polylogarithmic factors.
2 Related Work
In this section, we review related works from both setup and technical perspectives.
RL with Generalized Linear Function Approximation. There are recent efforts devoted to investigating function approximation beyond the linear models. Wang et al. [2021] investigated RL with generalized linear function approximation. Notably, unlike our approach that models transitions using generalized linear model, they apply this approximation directly to the value function. Another line of works [Chowdhury et al., 2021, Li et al., 2022, Ouhamma et al., 2023] has studied RL with exponential function approximation and also aimed to ensure that transitions constitute valid probability distributions. The MDP model can be viewed as an extension of bilinear MDPs in their work while our setting extends linear mixture MDPs. These studies are complementary to ours and not directly comparable. Moreover, these works also enter the computational and statistical challenges arising from non-linear function approximation that remain to be addressed. The most relevant work to ours is the recent work by Hwang and Oh [2023], which firstly explored a similar setting to ours, where the transition is characterized using a multinomial logit model. We significantly improve upon their results by providing statistically and computationally more efficient algorithms.
RL with General Function Approximation. There have also been some works that studies RL with general function approximation. Russo and Roy [2013] and Oshand and Roy [2014] initiated the study on the minimal structural assumptions that render sample-efficient learning by proposing a structural condition called Eluder dimension. Recently, several works have investigated different conditions for sample-efficient interactive learning, such as Bellman Eluder (BE) dimension [Jin et al., 2021], Bilinear classes [Du et al., 2021]. Decisiin-Essimaatin 2021], and Admissible Bellman Characterization (ABC) [Chen et al., 2023]. A notable difference is that they impose assumptions on the value functions while we study function approximation on the transitions to ensure valid probability distributions. Moreover, the goal of these works to study the conditions for sample-efficient reinforcement learning, but not focus on the computational efficiency.
Coefficient (DEC) [Foster et al.,
Multinomial Logit Bandits. There are two types of multinomial logit bandits studied in the literature: the
model, where the parameter is a vector [Cheung and Simchi-Levi, 2017] and multiple-paramen model, where the parameter is a matrix [Amani and Thrampoulidis, 2021]. We focus on the single-parameter model, which are more relevant to our setting. The pioneering work by Cheung and Simchi-Levi [2017] achieved Bayesian regret of ldVT), , where T denotes the number of rounds in bandits. This result was further enhanced by subsequent studies [Oh and Tyengar, 2019, 2021, Agrawal et al., 2023]. In particular, Périvier and Goyal [2022] significantly improved the dependence on K. obtaining regret of ((dvkT + k x in the uniform revenue setting. Most prior methods required storing all historical data and faced computational challenge. To address this issue, the most recent work by Lee and Oh [2024] proposed an algorithm with constant computational and storage costs building on recent advances in multiple-parameter model [Zhang and Sugiyama, 2023]. Their algorithm achieves the optimal regret of Ō(dVKT <T + x and (d + x=1) under uniform and non- non-uniform rewards respectively. However, although the underlying models of MNL bandits and MDPs share similarities, the challenges they present differ substantially, and techniques developed for MNL bandits cannot be directly applied to MNL MDPs. For example, MNL bandits, the objective is to select series of assortments with varying sizes that maximize the expected revenue, whereas in MNI. MDPs, the goal is to choose one action at each stage to maximize the cumulative reward. Thus, it is necessary to design new algorithms tailored for MDPs to address these unique challenges.
3

---

3 Problem Setup
In this section, we present the problem setup of RL with multinomial logit function approximation.
Inhomogeneous, Episodic MDPs. An inhomogeneous, episodic MDP instance can be denoted by a tuple MM = (S, A, H, {PA 1 fra H where S is the state space, A is the action space, H is the length of each episode, Py x A x - [o, 1] is the transition kemel with Py (s' s. a) is being the probability of transferring state s' from state and taking action a stage h. ra 8 A [0, 1] is the deterministic reward function. A policy т = [TA) is collection of mapping Th, where each T S + ((A) is function maps state to distributions over A stage h. For any policy
and (8, a.) E S x A. we define the action-value function Q7 and value function VA as follows:
H
(7 a)
E
Σ Lk==h
Th (sw,,w) aw) 8h an
(8) (-16) (0%
where the expectation of Q2, is taken over the randomness of the transition IP and policy x. The optimal value function Vi and action-value function 27 given by Vi sup, V (s) and (3.
sup, Q77 a). For any function V : S + E. we define [P,, (/ ) = Er (-1s,a) V(s').
Learning Protocol. In the online MDP setting, the learner interacts with the environment without the knowledge of the transition kernel (Px } We assume the reward function {rr]//=1 is deterministic and known the learner. The interaction proceeds in K episodes. At the beginning of episode kt the learner chooses a policy mr a h-1 At each stage h E [f], starting from the initial state 1 the learner observes the state 8k, chooses action dx, sampled from T (- $k.h), ), obtains reward
h=1-
|
r, ( (k,A) and transits to the next state 8k,4+1 ~ P. | (*.A) )) for la E [H] The episode ends when SH41 is reached. The goal of the learner is to minimize regret, defined as
K
Reg(K) K)
Ev EVT k=1
which is the difference between the cumulative reward of the optimal policy and the learner's policy.
Multinomial Logit (MNL) Mixture MDPs. Although significant advances have been achieved for MDPs with linear function approximation, Hwang and Oh [2023] show that there exists a set of features such that no linear transition model can induce a valid probability distribution, which limits the expressiveness of function approximation. To overcome this limitation, they propose new class of MDPs with multinomial logit function approximation. However, their work focuses on the homogeneous setting, where the transitions remain the same across all stages (i.e., P1 In this work, we address the more general inhomogeneous setting, allowing transitions to vary across different stages. We introduce the formal definition of inhomogeneous MNL mixture MDPs below.
PH).
Definition 1 (Reachable States). For any (h, s,a) a) E [H] S x A. we define the "reachable states" as the set of states that can be reached from state s taking action at stage h within single transition, i... Sh.eaa - {s' S (s s,aa) > 0}. Furthermore, we define Sh,e.o |Sh,e,el and denote by & (h,,a, Sh.e.o the maximum number of reachable states.
Definition 2 (MNL Mixture MDP). An MDP instance M = (S, (PP) [rk)M] 1) is called an inhomogeneous, episodic B-bounded MNL mixture MDP there exist a known feature mapping d(s') s,a): : S x A x S + I with (lø(s' |8, a)]ll < 1 and unknown vectors (0 [0 E O with
θ = (0 E d..d |101|2 < B}, such that for all a8,a, h) E S x A x (H) and s' E Sp it holds that
exp(o(s' (8) [s,a)Te;) T0
P s, EFES.... (x T,))
Remark 1. This model is consistent with models like neural networks [LeCun et al., 2015), where the feature ó obtained by omitting the final layer, and 0f represents the weights of the last layer. A final softmax layer is then applied to ensure that the output forms a valid probability distribution.
For any Rdd, we define the induced transition as PE., (0) Eses,, explo(s s.a) Øj. We then introduce the following two key -ebeeded quantities x and x that measure the effective non-linearity over the entire parameter space and around the ground truth parameter respectively.
exp(o(e' (.0) To)

---

Assumption 1. There exists 0
< < S K² < 1 such that for all (s, (s,a.h) E S x A [ and s' a as it holds that inface (0)p (0) 2 and p (%))p (0%) 2 K^
Assumption 1 similar to the assumption in generalized linear bandit [Filippi al., 2010] and logistic bandit [Faury et al., 2020, Abeille et al., 2021] to guarantee the Hessian matrix is non-singular. Finally, show the claim about the range of the magnitude of and x*
Claim 1. It holds that I/(U exp(2B))² < s x & 1/U2.
Statistically Efficient Algorithm
The work of Hwang and Oh [2023] first introduced the MNL mixture MDPs and proposed algorithm with regret bound -x==1xd12
However, as discussed in Claim I, follows that U² S < (U cxp() which results in the regret bound scaling polynomially with the number of reachable states U. In the worst case, U can be equal the size of the state space S, thereby undermining the motivation for function approximation, which aims to mitigate the dependence on the large state and action spaces. this section, we address this significant issue by proposing a statistically efficient algorithm that eliminates this dependence in the dominant term of the regret.
4.1 Parameter Estimation
In this section, first present the parameter estimation method based on the maximum likelihood estimation (MLE) for MNL mixture MDPs. Next, we review the confidence set construction based on the estimated parameters from previous work [Hwang and Oh, 2023]. Finally, we propose our new confidence set construction and highlight the improvements it offers over the previous approach.
Since the transition parameter 0% is unknown, need to estimate it using the historical data. At episode k. we collect trajectory {S2,, (k then define the variable: yk E {0, 1
where y 1l (d'=0LA41) for s' Sk. A Sen.n.o... and S |S We denote by x
pf aar, (0). Then ye.A is sample from the following multinomial distribution:
yk.k ~ multinomial(1, (f")......... *S (B*)))
Pk.h
where the parameter indicates that yk,, is single-trial sample. Furthermore, define the noise
< = yh.n pk (07). It is clear that 6s,A E [[1, 1|5,.,, E[ex,n] = and Evess, < = 0.
We estimate the parameter f% using the MLE and construct the estimator 0R,n as follows:
A 11012.
0 R.A
arg min Lx b (0)
Σ
Σ S'E,
-Vin log pi
(1)
DERd
where A is the regularization parameter. Though the MLE estimator 0 is the same that of Hwang and Oh [2023], the confidence set constructed differently. Specifically, define the gradient Gk.r (0) and Hessian matrix H4, (0) of the MLE loss by
#-1 1
(0) = Σ
Σ
(O) - Vi + A4O,
i=1 PES..
k-1
(0) = Σ Σ
(0)
(
Σ Σ Σ
10 + AeT.
i=1
PES.A
i=1
=''ESS,, s"ESi,h
Furthermore, we define the feature covariance matrix Ag, AA,
= x-
X I - Eres., (Pih)
By demonstrating H4 (0) 2 AA h.: AO E O, Hwang and Oh [2023] construct the confidence set as
C* = { {10 dalllan < /dlog(kH//)) A Bx
(2)
Since the radius the confidence set depends on -1 the final regret bound also exhibits depen- dence x To eliminates this dependence, construct k-independent confidence set based on
5

---

new Bernstein-like inequalities in Lemma 13, following recent advances in logistic bandits [Faury al., 2020, Périvier and Goyal, 2022]. Specifically, we show the following lemma.
Lemma 1. For any E (0, 1). ser & = cllog(HH/o) and define the confidence set as
Cn.h- { 0 (( PR.N (0.n(Ox,1.) (0x,
1l 1000 S (B +B+3) dllogg)))(HHH/))) 2 Be
(3)
Then, we have Pr(0% E Ck,N 2 8, vk [K]. [H].
Comparison to prior work. We compare the confidence sets defined in Eqs. (2) and (3).
For the confidence set in (3), by the self-concordance property of log-loss in Lemma 10, we have:
|| 0R. (l.) I (1 + 3/2) (0) GR. ( (O.W)) - ( (1+ 332)
Then, note that Hk, (0) - kAAk, for all 0 θ, we have
||0 A.. S -/3|| 1k. S K xx +B
(4)
Thus, compared the confidence set in Eq. (2) from Hwang and Oh [2023], our confidence set in Eq. (3) provides a strict improvement by at least factor of -1/22 This improvement one of the key components to eliminate the dependence on K in the dominant term of the final regret bound.
Additionally, identify a technical issue of Hwang and Oh [2023]. Specifically, they bound the confidence set in Eq. (2) using the normaizzd concentration in Lemma 12. However, the noise is not independent, and since Ee's,, EAA (due to the learner visiting each stage exactly once per episode), it does not satisfy the zero-mean sub-Gaussian condition in Lemma 12. We observe similar oversights in multinomial logit contextual bandits [Oh and Iyengar, 2019, 2021, Agrawal et al., 2023], an issue that, to our knowledge, has not been explicitly addressed in prior work. This issue can be resolved with only slight modifications in constant factors by a new self-normalized concentration with dependent noises in Lemma of Li et al. [2024b], a simplified version of Lemma 13.
4.2 Optimistic Value Function Construction
Given the confidence set Čg it is natural to follow the principle of "optimism in the face of uncertainty" and construct the optimistic value function. Hwang and Oh [2023] constructed the optimistic value function (s, a) by adding a closed-form upper confidence bound as follows:
Qu,((s, rn(s,a)+
Σ
(V,.)) + 2HB
max S'ESi.....
e'ESh.r.a
[0,H]
where (s) = max.ed (s) Then, a naive idea to compute the optimistic value function is replacing the radius of the confidence set 9 with & and the feature covariance matrix Ag, with the Hessian matrix (0)) However, there are two issues with this approach. First, the true parameter 0% is unknown thus the Hessian matrix H4, (07) is not computable in the algorithmic updates. Second, though B, is independent of and the Hessian matrix H4.n (0%) captures local information, the bonus term max [|o2/all;;
(0) remains in a global form. This term involves taking the maximum over all states E Sk,e,a which prevents fully utilizing the local information. To address these challenges, we construct the optimistic value function by directly taking the maximum expected reward over the confidence set. Specifically, we define Q a) and (s) as
@un(s, a) (s, + max DECo, s'ESh....
Σ
pe. (0)
(ien(s) max (s, (6)
(0,11)
aeA
This construction addresses the first challenge by eliminating the need for the Hessian matrix HA. (0;)
and directly leveraging the local information embedded in the confidence set Čk... For the second challenge, although we bypass this issue in the construction of the optimistic value function, we still need to address it in the analysis. To tackle this, we employ second-order Taylor expansion, in contrast to the first-order expansion used in the analysis of Hwang and Oh [2023]. This allows for more precise capture of local information. Further details are provided in Lemma 7 in the appendix.

---

Algorithm UCRL-MNN-LL
Input: Regularization parameter X, confidence width Byg confidence parameter d.
1: Initialization: Set 0,, 0, (1,)(,)) 0, ( 0 for all h E (H).
2: for k k= 1,..,, K do
3: for h = 1........ ...., H do
4: Observe current state s and select action d arg max (sk.h)
5: end for
6: Set V 1++1,1+1())
7:
for h= , do
Compute the estimator 1R+1.6 by Eq. (1) and update the confidence set Ex+1, by Eq. (3).
8:
9: Compute Qk+1,(()))) and (+) as in Eq. (6).
10: end for
11:
end for
4.3 Regret Guarantee
Based the parameter estimation in Section 4.1 and the construction of the optimistic value function in Section 4.2, we propose the UCRL-MNI-LL algorithm. At each stage h of episode k, the algorithm observes the current state Sk,4 and selects the action that maximizes the value function, i.e.,
dga = arg max A ( a), and transits next state 8-, After collecting the trajectory {sk,h, 01.h | the estimator 0R+1. is updated using Eq. (I), and the confidence set C2+11, is updated according to Eq. (3). Then, the value function QE+IA and V 1. are updated using Eq. (6). The detailed procedure is outlined in Algorithm 1. We show it achieves the following regret guarantee.
Theorem 1. For any 8 E (0. set X dllog(HH66) /8), and By (B 3) /dlog(k /8). With probability at least - 8, UCRL-MNL-LL algorithm (Algorithm 1) ensures the following guarantee:
Reg(K) Ö(dI2 H²)
Remark 2. Focusing on the dominant term, guarantee eliminates the problematic dependence
x-1, in stark contrast to the Oxx- VK) result of Hwang and Oh [2023]. As noted in Claim such undesirable dependence has polynomial scaling with the number of reachable states U. which can be as large the entire state space S in the worst case. This renders the guarantee for function approxinationnddeiineed for settings with large state and action spaces- essentilly vacuous.
5 Computationally Efficient Algorithm
While the UCRL-MNI-LLL algorithm is the first statistically efficient algorithm for MNL mixture MDPs, it computationally expensive dur the the optimization of the MLE in Eq. (1) and non non-convex optimization in Eq. (6). To address these challenges, we propose a computationally efficient algorithm in this section, which attains the same regret but with constant computational costs per episode.
5.1 Efficient Online Parameter Estimation
In this section, we focus on estimating the unknown parameter 0% a computationally efficient manner. We first discuss the storage and time complexities of the MIE optimization in Eq. (1). Next, we introduce an efficient online paramcter estimation based on online mirror descent that provides similar guarantees to the MLE, but with constant storage and time complexity per episode.
For the storage complexity, the optimization problem defined in Eq. (1) requires storing all historical data, resulting in a storage complexity of O(k) at episode k. In terms of time complexity. the problem does not have closed-form solution and can only be solved within an s-accuracy, such as using projected gradient descent. As discussed in Faury et al. [2022], optimizing the MLE typically requires ([log(1/e)) iterations to achieve an e-accurate solution. Since the loss function defined over all historical data, each gradient step incurs query complexity of O(k). As is usually chosen as 1 1/k for episode k, the total time complexity (k log k) at episode Consequently, both storage and time complexities scale linearly with the episode count, which is computationally expensive.
7

---

To improve the computational efficiency, the basic idea is to estimate the unknown parameter with the online mirror descent (OMD) update instead of the MLE as defined in Eq. (1). To this end, we first define per-episode loss function (0), gradient & (0) and Hessian matrix HK, (0) as
fr (0)
Σ
vi log (0), gK.((() V V(
Σ S'E
(E (0) via Jo
(7)
z'ESe,h
(0) = ( = E PEA
E Σ
(1) (
o d'ESE.A
ef E'ESE, e"ESk.
Then, the design of the OMD algorithm can be conceptually divided into two parts: the approximation of the past losses and the approximation of the current loss. We provide the details of each below. Approximate the past losses. To integrate historical information from previous iterations while avoiding the use of MLE in Eq. (1), construct the estimator 1k+1,h using the implicit OMD form:
0.+1,6 arg min AED
110 f H
2n
where 1) is a step size and He. & Fl (fx+1.)) = -E=1 H (8 + A The optimization problem can be decomposed in two terms. The first term is the instantaneous log-loss lx (0), which accounts for the information of the current episode. The second is a regularization term that ensures the current model remains close to the previous one, OR,A. thereby incorporating the historical information acquired so far. The most critical aspect in the above is the design of the local norm He which intentionally approximate the per-episode Hessian matrix by (0,,1,,) a look ahead point 1, Such Hessian matrix, originally introduced by Faury et al. [2022], effectively captures the local curvature of the loss function and is crucial for ensuring statistical efficiency.
The update rule in Eq. (8) is storage efficient, as it only requires storing the Hessian matrix Har which can be updated incrementally, resulting in an ((1) storage cost. terms of time complexity, the optimization problem in Eq. (8) suffers an O (log k) time complexity at episode k; since the loss function is defined only over the current episode. While this represents a significant improvement over the (l log k) time complexity of the MLE in Eq. (I), there is still need to reduce the cost further to (1) per episode, particularly given the potentially large number of episodes.
Approximate the current loss. To achieve ((1) time complexity per episode, we can further approximate the current loss with a second order approximation. Drawing inspiration from Zhang and Sugiyama [2023], we define the second-order approximation of the original loss function lx, (0) at Oz,5 as (0) Ex.1 (Or,n)) + a (0,,,), 0s.n) + 1 1100 0v, (O..)) where 0g, a. is the
current estimate. Then, we can replace fr. (0) with its second-order approximation &g (0) in the optimization problem in Eq. (8). This leads to the following approximate optimization problem:
L = arg min (VEN,)(ONN))
Fe,n) + 2n
-10- 0g.h 11 Ne.
8Ee
where 1) is the step size, He, = Hr. + HH., (On,.) and HA. Σ H + AgT. Then, Eq. (9) can be solved with a single projected gradient step with the following equivalent formulation:
8 = a. म (O..n. ŌRTLA arg min| 1, Ha.n"
0EB
Thus, Eq. (9) is computationally efficient, as it only suffers ((1) storage and time complexity.
Notice that the update rule in Eq. (9) actually a standard online mirror descent (OMD) formula,
0 1 arg min
(Vl,, (#n,)),) 0) + D (0.60..))
(10)
17
where the regularizer is (0) |0 and Des (..)) is the induced Bregman divergence.
He.
Therefore, we can construct the confidence set building upon the modern analysis of OMD [Orabona, 2019, Zhao et al., 2024]. Specifically. we can construct the x-independent confidence set as follows.
Lemma 2. For any E (0, 1). set 17 = 1 log(1 (1 + +U)+ (B + 1) and A = 84 (B + d), define
Č., {0 θ |10 Ge. Me [8k] }
where BR OVVilog U /8)). Then, we have Pr[0 E C.,, 2 1 - 5, Ak E [K], h E [M].
Remark 3. Compared to the confidence set in Lemma 1, the radius 33 Lemma includes an
additional log U factor. This is due to our approximation of the original MLE using the OMD update.
8

---

Algorithm 2 UCRL-MNL-OL
Input: Step size 7, regularization parameter X, confidence width 8y, confidence parameter 8.
1: Initialization: 11,h XI, 11, h 0 for all h E [H].
2: for k == ==,...., K do
3: Compute Qx, in a backward way as in Eq. (11).
4: for h ....,. H do
5: Observe state hk,h, select action 0k = arg max Quch (sk,h,
6: Update Heg = Ha.n + H
7: Compute 0k+1,h arg mingee VVRn, (0x,)), Bknn) + 2 Bx Bl.
8:
Update HA++1 HA, + (0
9: end for
10:
end for
5.2 Efficient Optimistic Value Function Construction
Although the optimistic value function in Eq. (6) preserves local information effectively and provides strong theoretical guarantees, computationally intractable due to the need to solve a non-convex optimization problem. To address this challenge, we propose an efficient method in this section.
The key idea is replaces the operation of taking the maximum over the non-convex confidence set. While this idea has been used in bandit settings, fundamental challenges arise when applying it in the MDP setting. Specifically, Zhang and Sugiyama [2023] studied the multi-pare parameeerrt MLogB bandit, where each outcome associated with a distinct parameter vector. In contrast, MNL mixture MDPs involve single shared parameter vector across all outcomes. This distinction leads to a more complex Hessian matrix, necessitating more sophisticated analysis. A direct use of their analysis will leads polynomial dependence on the number of reachable states U, which is undesirable in the MDP setting. MNL bandit, which more closely related to
second-order Taylor expansion derive closed-form bonus term, which
Lee and Oh [2024] focused on the our setting. However, they construct the optimistic value function by directly taking the maximum over the confidence set, a computationally intractable approach in the MDP setting. As a result, they can apply second-order Taylor expansion around the ground truth parameter 0% in their analysis, while we must apply it around the estimated parameter 0k,r to construct the bonus term explicitly.
For MDPs, we show the value difference arising from the transition estimation error as follows. Lemma 3. Suppose Lemma 2 holds. For any V S - [0, H and (h, s, E [H] S x A, it holds
Σ
Σ
ve (o)V(()
fat < 6 + c2200
S'E
e'ESn
where
fet Gau
13
Σ
Páu (kin
Σ
cod Ca
5 H
max
I1 I Ia
2
""EShane
Based on Lemma 3, we construct the optimistic value function as follows:
an) [))(s,a)+ Σ Ol. + e +
fst
6
and
(11)
S'ES....e
[0.H]
where (x) max 2 h (8, a). In contrast to the value function in Eq. (5), which incorporates the term maxy 10 | the refined value function in Eq. (11) replaces it with c + c
This modification better preserves local information, offering a more accurate estimation error bound.
5.3 Regret Guarantee
The overall algorithm UCRL-MNN-OL is similar to UCRL-MNL-LL, but with the estimator and optimistic value function updated in a computationally efficient manner. The detailed algorithm presented in Algorithm 2. We provide the guarantee of UCRL-MNL-OL in the following theorem.

---

Theorem 2. For any 8 E (0, 1), set - Ololoo 7 log(1 +U) + 1) and x 84v2n(BB d), with probability least 1 - 6, UCRL-MNL-LL (Algorithm 2) ensures
Reg(K)= - ÖddH' +
Remark 4. UCRL-MNL-OL attains the same regret as UCRL-MNL-LL, but with constant compu- tational cost per episode. This is achieved by constructing an efficient online estimation based on OMD and an optimistic value function by closed-fore foom bonus instead of the non-convex optimization.
6 Lower Bound
In this section, establish the lower bound for MNL mixture MDPs by presenting a novel reduction, which connects MNL mixture MDPs and the logistic bandit problem.
Consider the following logistic bandit problem [Faury et al., 2020]: at each round t [T'. the learner selects an action 2y E X' and receives reward re sampled from Bernoulli distribution with mean u(x" 8*) (1 + exp(-z 0*) ()= where 0 {0 E Rº 1|0112 S. B} is the unknown parameter. The learner aims to minimize the regret: Reg (T) = max Et= p(xT0') 0*) -E (x)
Theorem 3. For any logistic bandit problem B, there exists an MNL mixture MDP M such that learning M is as hard as learning H/2 independent instances of B simultaneously.
Corollary (Lower Bound). For any problem instance {0% H and for K 2 d'x', there exists an MNL mixture MDP with infinite action space such that Reg( 2 M(dH (ddHVKK)) KKr).
Remark 5. Corollary also implies problem- independent lower bound of ((dHvK) directly. Corollary 1 can be proved by combining Theorem and the ((dVTkk) lower bound for logistic bandits with infinite arms by Abeille et al. [2021]. To the best of our knowledge, a lower bound for logistic bandits with finite arms has not been established, which is beyond the scope of this work. This absence leaves the lower bound for MNL mixture MDPs with finite action space open through this reduction. However, after the submission of our work to arviv [Li al., 2024a], a follow up work by Park et al. [2024] proposed a new reduction that bridges MNL mixture MDPs with linear mixture MDPs by approximating MNL functions linear functions. Leveraging this new reduction, they established a mooblem-independen (ddHF3/2 / /K) lower bound for the finite action setting. This achievement confirms that our result is optimal in d and K, only loosing by an O (2H)/2 factor.
Dependence on H. By the discussion in Remark 5, we note that our result is optimal with respect to d and K, but loosing by an 1/2) factor. We discuss the challenges in improving the dependence on H. Notably, MNL mixture MDPs can be viewed as generalization of linear mixture MDPs [Ayoub et al., 2020, Zhou et al., 2021]. The pioneering work by Ayoub et al. [2020] achieved a regret bound of (ddF2 for linear mixture MDPs, which matches our results in Theorem 1, differing only on the lower-order term. Later, Zhou et al. [2021] enhanced the dependence on H and attained an optimal regret bound of O(d/H3K) This was made possible by recognizing that the value function in linear mixture MDPs is linear, allowing for direct learning of the value function while incorporating variance information. contrast, the value function for MNL mixture MDPs does not conform to a specific structure, posing significant challenge in using the variance information of value functions. Thus, it remains open whether similar improvements on are attainable for MNL mixture MDPs.
Conclusion and Future Work
In this work, we addressing both statistical and computational challenges for MNL mixture MDPs. which leverage MNL function approximation to ensure valid probability distributions. Specifically,
we propose a statistically efficient algorithm that achieve a regret of Oddl'' + x x2 eliminating the dependence on x- in the dominant term for the first time. Then, we introduce computationally enhanced algorithm that achieves the same regret but with only constant cost. Finally, establish the first lower bound for this problem, justifying the optimality of our results in d and K.
There are several interesting directions for future work. First, there still exists a gap between the upper and lower bounds. How to close this gap remains open problem. Besides, we focuses on stationary rewards this work, extending MNL mixture MDPs the non-stationary settings and studying the dynamic regret [Wei and Luo, 2021, Zhao al., 2022, Li et al., 2023] is also an important direction.
10

---

Acknowledgments
This research was supported by National Science and Technology Major Project (2022ZD01 14800) and NSFC (U23A20382, 62206125). Peng Zhao was supported in part by the Xiaomi Foundation.
References
Yasin Abbasi-Yadkore Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NIPS), pages 2312-2320, 2011.
Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3691-3699, 2021.
Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 3 310()): 737-750, 2023.
Sanae Amani and Christos Thrampoulidis. Ucb-based algorithms for multinomial logistic regression bandits. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 2913-2924, 2021.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 463-474, 2020.
Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 384-414, 2010.
Nicolò Campolongo and Francesco Orabona. Temporal variability in implicit online learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
Zixiang Chen, Chris Junchi Li, Huizhuo Yuan, Quanquan Gu, and Michael I. Jordan. A general framework for sample-efficient function approximation in reinforcement learning. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
Wang Chi Cheung and David Simchi-Levi. Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available at SSRN 3075658, 2017.
Sayak Ray Chowdhury, Aditya Gopalan, and Odalric-Ambrym Maillard. Reinforcement learning in parametric mdps with exponential families. In Proceedings the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1855-1863, 2021.
Simon S. Du Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 2826-2836. 2021.
Louis Faury, Marc Abeille, Clément Calauzênes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3052-3060 2020.
Louis Faury, Mare Abeille, Kwang- Swang-SSnggTa Jun, and Clément Calauzènes, Jointly efficient and optimal algorithms for logistic bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 546-580, 2022.
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Moham- madamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirsze7, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 477 2022.
11

---

Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23 (NIPS), pages 586-594, 2010.
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. ArXiv preprint, 21 11112.144 13487, 2021.
Taehyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 7971-7979 2023.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2137-2143, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryooseñi. Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 33406-13411 2021.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 2015.
Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. In Advances in Neural Information Processing Systems 36 (NeurIPS), page to appear, 2024.
Gene Li, Junbo Li, Anmol Kabra, Nati Srebro, Zhaoran Wang, and Zhuoran Yang. Exponential family model-based reinforcement learning via score matching. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.
Long-Fei Li, Peng Zhao, and Zui-Hua Zhou, Dynamic regret of adversarial linear mixture MDPs. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 60685-607 11, 2023.
Long-Fei Li, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou. Provably efficient reinforcement learning with multinomial logit function approximation. ArXiv preprint, 2405.17061 2024a. URL https: / //arxiv...v////// org/ abs/ 2405. 17061v1.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Improved algorithm for adversarial linear mixture MDPs with bandit feedback and unknown transition. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3061-3069, 2024b.
Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits, In Advances in Neural Information Processing Systems (NeurIPS), pages 3145-310 3155, 2019.
Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI), pages 9205-9213, 2021.
Francesco Orabona. A modern introduction to online learning. ArXiv preprint, 1912. 13213, 2019.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems 27 (NIPS), pages 1466-1474, 2014.
Reda Ouhamma, Debabrota Basu, and Odalric Maillard. Bilinear exponential family of mdps: Frequentist regret bound with tractable exploration & planning. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 9336-9344, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35 (NeurIPS), pages 27730-27744, 2022.
Jaehyun Park, Junyeop Kwon, and Dabeen Lee. Infinite-horizon reinforcement learning with multi- nomial logistic function approximation. ArXiv preprint, 13633, 2024.
12

---

Noémie Périvier and Vineet Goyal. Dynamic pricing and assortment under contextual MNL demand. In Advances Neural Information Processing Systems 35 (NeurIPS), pages 3461-3474, 2022.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems 26 (NIPS), pages 2256-2264, 2013.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam,, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, pages 484-489, 2016.
Quoe Tran-Dinis Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self- concordant-like cost functions. In Proceedings of the 3rd International Conference Modelling, Computation and Optimization in Information Systems and Management Sciences, pages 155-168, 2015.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism rein- forcement learning with generalized linear function approximation. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Chen-Ye Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 4300-4354, 2021.
Lin Yang and Mengdi Wang. Samplc-optimal parametric Q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 6995- 7004, 2019.
Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems (NeurIPS), pages 29741-29782, 2023.
Canzhe Zhao, Ruofeng Yang, Baoxiang Wang, and Shuai Li. Learning adversarial linear mixture Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online Markov decision processes. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26865- 26894, 2022.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi Zhi-Hua Zhou, Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 - 52, 2024.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Proceedings of the 34th Conference Learning Theory (COLT), pages 4332-576, 2021.
13

---

A
Notations
In this section, we collect the notations used in the paper in Table 2.
Table 2: Notations used in the regret analysis.
Notation
Definition and description
CA (0)
Exesen Uh log Pi (0), per-episode loss function at episode and stage h
(0)
(0) = E''ss, (0) vi.n ) gradient of loss (0))
Hs,
EVSSA (0)6f ( Ev.es,, Evrese (000
(0)
ΣE (0) + 2 10133 the cumulative MLE loss
(O)
VLRA = EX=T Eves, (E vi,n dotn AnO, gradient of LR, (0)
(0)
V2C EtE (1))(0) AęLa. Hessian of MLE loss (0)
arg mingeR' Lk.A (0), the MLE estimator at episode and stage h
Harh
H4. (1,,h0111,,h) E H Aa the cumulative look ahead Hessian
Hugh
Ha.h nH (On,n), the of look ahead Hessian and the Hessian of current loss arg mingee / Ea, 0 Ten) + 2
the OMD estimator 0v. 11 Re.."
B Properties of Multinomial Logit Function
This section collects several key properties of the multinomial logit function used in the paper.
Without loss of generality, assume VSh, 3šh.e.o. E Shh such that @f s, a) 0. Otherwise, we can always define a new feature mapping ø'(s" 8, 3. = ø(s' s,a) o(s" " s, a) for any s" E Sa,s,a such that 6' (s's' a) 0 and the transition kernel induced by d' is the same as that induced by 6. Furthermore, We denote the set Sn,e.a Sn.e.a {...
First, we introduce the definition of self-concordant-like functions and demonstrate that the MNL loss function is salf-concordant-liee
Definition 3 (Self-concordant-lll function, Tran-Dinh et al. al. [2015]). A convex function f E C3 (TRm) is M-seeffconccrrdantliii like function with constant M if:
(s) & M [bbl///
for and M O, where (s) := f(a + sb) for any a, b R
Proposition 1. The per-episode MNL loss 4.. (0) and the cumulaaive MNL loss Cx.) are both 3 (y2sself-omncorrdnntiikee for all k [K], h [H].
Proof. By proposition B.1 in Lee and Oh [2024], the per-episode MNL loss function lx, (0) is 1//2seef--onncrdaat-ll/ Then, the cumulative MNL loss function (x) is the sum of self- concordant-lics functions and quadratic function, it is also / wto.self-commorraat-ll
Lemma (Zhang and Sugiyama [2023, Lemma 1J). Let ((2 = E 1 k} log i>اx)i
where (z)) R
[ {0) U [K] and b EK where C' 0. Then, we have
((a, 3) 2 ((b, v) + Vi(b, T( T(a (a-b) +
log K + 1) + 2 +1) (a b) T>? y) - -b).
14

---

Then, we show the Hessian of the MNL loss function is positive semi- cemiddefnite. Lemma 5. The following statements hold for any k E [K], E [H]:
(1) = Σ
(0)( Sish (0) (0) ZR E
J'ESE.A
B'ESE,
Proof. First, note that
Ya, y RR (x (x -0) xxx
yy
xz
yr
+ yy
xy
+ yz
Then, have
(0)
E PLo
Σ
E
s'ESe,
S'ESu, S"ES
Σ Pl)
Σ
Σ
O1 ( + (iT(OENN
2
8'ESe,h
d' e'ES2,
=
Σ
Σ
E
P(. ( (iT(T)"
8'ESt, 8"ESu.
Σ
(0)
E
E
S'E
S'ES.. 8"Eše,n
= E
p
Σ
Thin (0)
d'ESUM
d'ESu.
E
dn (0)
=
S'SU
KK Σ
(
S'ESEA
where the last inequality holds by the definition of in Assumption 1. This finishes the proof.
Next, we show several concentration inequalities commonly used in the analysis.
Lemma 6. Suppose A 2 for any k E [K], h E [.],for the quantities in Table 2 and define
th = Vi Σ
Thin ohhn Σ
ph:n (1
Then, the following statements hold:
h: X
(O) 112 (22, I 2dlog 1
1=1 d'ES..
b A
(II)
Σ Σ
(0. B Mfe,, S 2d |+
d'E
1+ k
k.) And
(III)
S 2d 2d
S.E..
2dlog
2 (1+
h
(IV)
max EES.
HE)())
K
Apd
4O E
(V) max FESLa
|
- H-1 S 2d
|
k
Aad
15

---

Proof. We prove the five statements individually.
Proof of statement (I). By the definition of H.,,(0), have
(0)
Σ (OE
Σ
Σ
Pl
s'ES.,
S'E,, S'ES
(E 10,, (p) (0
= (.EEpI [00 (0 (o - Epr)
(12)
Thus, we have (0%) 2 EvES,A ( Then, get
H441,, = (1,) + E PLM(01)((NN
S'ES
As result, we have
del(H det(Hs,
E PL, P. (2,,1110)))
e'ES..
Since À 2 1, we have Eres, Pi, (o 12 (10g)
1. Using the fact that S 21og(1 + 2) for
any [0, 1). we get
Σ Σ
Pi, (0) (7 (0:)
2 Σ log (1+
Σ
(1) (1
1=1
e'ESt.
(det(Hls1IN(0))) (det(H2,,((h)) k
S 2 2og
2dlog
1+
Xd
where the last inequality holds by the determinant inequality in Lemma 14.
Proof of statement (II). The proof same as that of (I), except that we replace 0% with 0.41,
Proof of statement (III.. By Lemma 5, we have (0) = Ev'esh pÊ (0) anch (0) (T The remaining proof is the same as the proof of statement (I).
Proof of statement (IV). By Lemma 5, we have v0 E O, it holds that Ho+1,1 > Ha. (0) E.'rSn oh ( T. Since À 2 1, we have max I1 ( S K. Using the fact that s 2og((1 2) for any 2 [0, 1]. By similar analysis as the statement (I), we have
k
max 10 M
2
log (1 K. max ( SEE
1=1
2
log 1 +
Σ
K
1=1
S'ES.
2
det det((Hx+1,
log
det(HH,,n (0))
2
k 1+
d log
k
Xd
This finishes the proof of statement (IV).
Proof of statement (V). By (12), we have
H..n(0ea2 = Σ Pr PLA(OHIWW@WANAAA E Σ
S'E
S'ES
Thus, we have
H Ha,h + K
Σ
Then, the remaining proof is similar to the proof of statement (III).
16

---

C Useful Lemmas for MNL Mixture MDPs
In this section, we present some useful lemmas that commonly used in the analysis.
C.1 Useful Lemmas
Lemma 7. For any 0, 82 E Rd and positive semi-definite matrix A, suppose ||6, -2lla S B. Then, for any : [0, H] and (h,,,a) (H) S A, it holds
Σ Pa. (O:)V(s))
E Pro (82)
lat 2nd S
S,a S.
S'ESt...
SS
where
1st 9,a
= HB Σ
pd P
Σ
A-1²
s'ESh.n.
s"ESb.r,a
5 H max
2nd
2
Lemma 8. Suppose v(k: h 8, a) K [H] S x A and OR,h E TR., it holds that 0% Cr where
Cx,1 {0 Σ
((( E (0)( S &Tahau
(13)
S'ESp.
S'ESn.o.e
Define
@x,((s,a)= = (a((saa)+ + arg max
Σ (
(14)
DECx.
S'ESn
[0,H]
or,
(x) = [Ta(e.a)+
Σ DEN + +a
(15)
10.m
S'ESa..
where Vi. (s) max (s,(s, for any E (0, 1), then it holds that
a). Select the action ak,h arg max Qu a). Then,
(s) S Qu,( S (n(s,a) + PP (s, + k.h.a.
Lemma 9, Suppose Lemma holds. Then, it holds that
K
H
Reg( K) 2
+ H /2KH log(2/8).
1=1
C.2 Proof of Lemma
Proof. By the second-order Taylor expansion 0,, there exists 0 v0 + (1 v)02 for some E [0, 1]. such that
Σ (O)(V s'ESu,naa
Σ (O))V())
S'S
(01) (02 (sV + 2 S'ES
Σ
(02 102-84 81) T VVPpi (.)
S'ESh.a
The gradient of (0)
(0) is given by
Vp (0) (0) Po)
Σ
(0)
s'ESh.ni
17

---

For the first-order term, we have
Σ
V (0220()))002-011)
d'ESn.ea
Σ
(0)((0)
T(2 01)V(s))
E v E
(0 01)V(6)
d'
S HH
Σ
V (01)
(0 ((22 - -0,)-
Σ
Peja ( (0))))( 2,00 (T T(2= - 01)
8" S"ESh,ra
(00
T (02 - 01)
= . Σ
P (0))
(0) s,a)
8'E8
S H
Pe (0))
Pa (0) (0))0""a
A-1 || /|02 - 01111, 81lla)
5.0
s'ES hi
S HH
Σ
Pe (01)
03.n
Σ
P (0g D0""
A-
s"ESkia
< H3
Σ
(0,)
Σ
Pe (0,))0 9.a 1
(16)
S'ESa.
where in the first inequality, denote St as the subset of Sa, such that ( (022 01)
Eeres... P... (02)())"))) (022 - 01) is non-negative, the second inequality holds by the Holder's s inequality, and the third inequality is by the condition ||0, 02 S B.
For the second-order term, let ug (0) = (d%(a) T and pE (u) = I- exp(xx")) exp(xut)) further define
exp(ust.)
exp(ugga)
(V
F(u)= = Σ
F(u) Σ 1 I+ENEESh... exp(us")
Σ E8"an exp(ux"a)
8'ESn.r.a
S'ESb
Then, we have
1
Σ
(02 (02-01) ( -115000000000000
2
1
(u(02)= - u((1)) T -2 v2 - u((1))
=
2
(F(((()))
Σ
(0)) we'd (01))
(0))
(02) (0)))
2
Os'Os"
St... 5" ESh.nia
H
(F(((())
<
Σ Σ
Ju (02) ug (01)
|ut". un"n (02)
2
Os'Os"
S'. S'ESk...
where the inequality holds by (ss) E [0. HI, Vs.
According to Lemma 17, we have (omit the subscript Sp,s,a for simplicity):
H
PF(((())
s,a (0z) - vh ( Os'Os"
1 (0(((1)) -."h
2
<
Σ
a,a (02) unia (0)) p (u( (u())) |uE"a(0)) - (0))
8/
3H
+
Σ
(
(a (92) -. (B:)) pi (u(²)).
(17)
2
x
18

---

To bound the first term, by applying the AM-GM inequality, we obtain
H
Σ
un (f1) p ((. (u(8)) -u (8)) -w (01) psi (n(0)) (u(8) |us" (02) - u3ta (0))
(02)
8'
82
- 2
H
Σ
(u (02)
u (01)) Ps.a (w(0))p
H
(ug (82) (0 ps (e((((()) ((()))
S H
Σ
(1
(82)
u (01)) 2 Va (u(o)
(18)
Plugging (18) into (17), we have
H
(02) (0)) FF(((())
Σ
|12 (02) - -u,"a (0:)
2
Os'Os"
8"
5H
(u (0z) -u
- (0)) P (u(0)
2
5H
((ot(a) T T(02 (022-11))) -11) (u())
2
5H
g2
max
5 9,4 A-1,
(19)
2
where the last inequality holds by the condition ||0: - -2llA S B.
Finally, combining (16) and (19) finishes the proof.
C.3 Proof of Lemma 8
Proof. First, we prove the left-hand side of the lemma. We prove this by backward induction on
h. For the stage h H, by definition, we have QR (s, a) = TH (s, a) = Qi (s, a), +
0 == (*)) Suppose the statement holds for h + 1, we show it holds for h. By definition, if
Q a) = H1 this holds trivially. Otherwise, we consider two cases:
For (s, a) defined in (14), we have
( a) = rn (8, a) + arg max 8ECx.
Σ (o)
8'ESh.r.
2 (x) + arg max BeCx,
Σ d'ES
pe (0)V
a8) + Σ ViV ())
d'ES
where the first inequality is by the induction hypothesis, and the second inequality is due to 0% E C.
For (s, a) defined in (15), we have
Qun(s, a) = (s( +
Σ
Ps.a (x Ve. + Theaa
S'ESh
2 (n( +
Σ
Ps.a
Phaa
S'E
2 a)) +
Pa.a Pr,(0 Ve.44 (/)==/) = () a).
s' S'ESp
19

---

where the first inequality is by the induction hypothesis, and the second inequality is by (13).
Then, prove the right-hand side of the lemma.
For (s, a) defined in (14), have
Qua(ss, a) = rn(5, a) + arg max
Σ
(o
DECk,
S <ra(s,a)+
E
S'ESn
<r)(s, +
Σ ( 2
s'ESp
where the inequality is by (13).
For (8, a) defined in (15), we have (R, a) rr(s,
Σ (a, Tk.b...
s'ESn.ria
3 <r((s, +
Σ
(1) + 2T h,
s' S'E
where the inequality is by (13).
C.4 Proof of Lemma
Proof. By the definition that Reg(K) Σ (s - Ex= k== Vi (5k,1).
have for any
E (0, 1), with probability at least 1 - 8, it holds that
K
K
K
K
Σ (sR,
Σ (sk,1) = Σ
Σ (s2,1)
k=1
K
K
( x (sk.1) - Σ ViTh (sk.1)
kml
km
(sR,1, Σv' (sn,)))
where the first inequality is by Lemma and 0% CeA with probability at least 1 1- ò, and the second inequality is by action selection dg,A arg max ( By the right-hand side of Lemma 8, we have (1R, 1x - (s2.1)
-r(sk,1, (x,1) + P. (8M, (n,1) 1) + 21 h.s -(k,, (x,1) -P PIV22 (82,1, ax.1)
< PP.(V - 1/2 (5k.1, 1x - (Vr.2 - ((*x)(xx.2) + (Vr. - V22 (sk,2) 2T 1. 106,
< PPi - V. (5kk11 ak.1) -VV.22 - (5x.2) + (Q2(5k.2 ax.2) V2 (Sk.2))
+ 2D 2T he
Define MA, = PA (V (VE WTTH (sk,h, ak,h) (Vr,441 Vi (5k,6+1). Applying this recur- sively, we have
@1(s)1, V7** (sk,1) 2 These +
Mr
Summing over kt we have
K H
K
K H
Reg(K) (K) 2
T
M
<
Σ
T
h.s. + H 22//KHolg222//
Rr Pumm
Arm Am
Amm Am
where the inequality holds by the Avuma-Hooffding inequality as Ma a martingale difference sequence with Ma.h 2... This finishes the proof.
20

---

D Omitted Proofs for Section 3
D.1 Proof of Claim 1
Proof. First, by the definition of MNL mixture MDP, we have V(8,a) x and E Sp.e,a>
it holds that (0, 2 (xp((BB)/( exp( vo E R. thus x² 2 2 1/(U exp(2B))² Next,
consider the state-action pair (s, a) at stage with the maximum number of reachable states U, it is clear that Exes..... pe (0%) = 1. This implies that Evesh... Exress.... P. (0,, (p (0)) = 1. Applying the pigeonhole principle, there exists s', s" E Sh,s.a such that Pi (0))) (0)) S 1/U2. Thus, conclude that K S x* 1 1/U2. This finishes the proof.
E
Omitted Proofs for Section 4
E.1
Useful Lemma
Lemma 10. v01.0> 0g O we have 0211va, & (1++32)][Qa000) Gn.n
Proof.
By the multivariate mean value theorem, we have
(0i) - (02) = V V. f LL + -22)ddt(0 02).
Hence, we have
|9((0)) 9(02))l
110 0211ca,(00,,02)
where Ck,n 1or v2 (02+ dt) By self-concordant-like property of Cr,, in Proposition 1, we have Ha.n (01) 3 (1 (1+3v2) (0,, 02). As a result, we have
||0, - 02 021l _ (1+3/2) 1/2 10: -
= =(1+3/2)4 1/2 19 (6)) - gn.N (02) (02) (82)llan $ + 3v 1GR, (01) GN. (02) (02)) (e.)))))
This finishes the proof.
E.2 Proof of Lemma 1
Proof. Since oR.b minimizes LE, (0), we have Gi,n = O. Thus, we have
A-1
(B,) Iv.n (Ga,n)
Σ
Σ (FE Vi'no A + Ag
d'ESLo
Therefore, since |10 B and (4,) 2 ARI, for any 8 E (0, 1). with probability at least 1
|| - GR, Gr,n (o.. x
Σ
Σ
+ V
i=1 s'ESi.
Vx
4
Hd det (HH,A(())) X VARB
log
/x
where the last inequality holds by the Bernstein-type concentration inequality in Lemma 13. Then, by the determinant inequality in Lemma 14, we have det (eetHH,, (0t) s (As +
5)²² Thus, obtain
- Gv. (02 11 < B (B+)) Vxe
2
kH
V log
1
8
dAR
By the configuration that A dl log (oggk////) /8) and applying the union bound for h E [H]. have with probability at least 8. for all h E [H] simultaneously. it holds that
[G - (v.n Il (0)) S (B + 3) +d) (olog((H//))
This finishes the proof.
21

---

E.3 Proof of Theorem 1
Proof. By Lemma 10, with probability least 8, it holds that
|10,.1 6% (1ll (0t) I (1 + 3v2) Gr. (Ox,,)) Gx,n (n (gg) S (1+ 3v2)
where the last inequality holds the confidence set C. in Lemma 1. Then, by Lemma 7, we have
Σ
E
Ps (O))
S c + end
K'ES
S'ES..u
where
1st = (1+
Σ
Pa 1
Σ
||
S"ESh
2nd 5,a
90H B max 1 (1.)
By Lemma 9, we have
K
K H V (sk,1) 2
Σ
kR +
lat
2nd ck + H
HHHKKHH log(2/8)
(20)
R= 1 Am1
Next, we bound
d.t and 6K, respectively.
Bounding
1st
By statement (I) of Lemma 6, we have kih'"
Σ
( - Σ (
k= o' A
S"ESa
Σ
Σ
(0%)
Σ Σ
Ph (0%)
(8))
E Ph", 12
S'E
K
2dK log 1+
dÀk
By the configuration that
3x (B + 3) /d llogk//)), we have
ΣΣ
R.
< (1 33 K log (1+ ddx
K
log
)
k
(21)
2nd Bounding 6
By statement (IV) of Lemma have
K
H
K
2nd k.
9
max|| 1a (
h=
k=
180
K
H 3d dog log
11
ddx
180 (B + 3)2 P 2² log 1+ K
K
log
(22)
dd
where the first inequality holds by sum max.ess. 11 20)
- 2d log
(1
Azd
#
4A
E
in Lemma 6 and the second inequality holds by the configuration of 3x. Combining (20), (21), and (22), we have with probability at least
1+ ddx )
K
180 +
(B+3) log 1+
K log ddx
K
Reg K) < V 2dK log
K
< δ [dH + x 1 (2
This finishes the proof.
22

---

Omitted Proofs for Section 5
F.1
Useful Lemma
Lemma 11. For any E [K], [H], define the second-order approximation of the loss function --0.0))+1--..---0-000000 Ha, (0...)
(x (0) at the estimator Ok.h as & (0) a
Then, for the following update rule
OK+IA = arg min (0)
100 11
DE
2m
it holds that
k
11
0%
Hot1k
S2n
Σ
(0%) - Σ (ca(Oet1.h)) ) + 4AB
+ 12V2BB
> 10 02,1112
> 10 B.. B.lllB
Proof. Based on the analysis of (implicit) OMD update (see Lemma 16), for any i E [K], we have
(Vli, (0.. 1,)), 1.41.1 0%) < (10.,. 1l 10:41, - -4. 11 02,t (
According to Lemma 4, we have
f,, lu, (0%) < (V4,)(0422,,)0111 -0% 1 |10 07 -
where (= log(K + 1) + 4. Then, by combining the above two inequalities, we have li, (0.+1.n)) - C, (0,) < (Vli,
6 (0.+1.))) (10L. 1 110+1,1 - 0g 110 Oun 1Pe.))
0%)
We can further bound the first term of the right-hand side as:
(1e1,( - (0 0:t1,6 0%. (V(1n(0++1.))) (Oc,))) 2 (0,, (0++1,h 0i,n), D.+1, - 0%)
(E+1),(E+11) 00. p,,, 01+1, 0%)
-3V2|(0,111. - 1/-11100-1.1 -
< 66V2B|1041.. - 12.
where the second equality holds by the mean value theorem, the first inequality holds by the self- concordant-like property of (-) in Proposition 1, and the last inequality holds by 0 and 6% belong to θ = (0 E R2 |10||2 < B}. and ( > la-
Then, by taking the summation over and rearranging the terms, we obtain
&
00 - 0% HEFIA
<<
Las (0%)
Σ
Ca.u (anh(B+t1.))) + 1102, 0
==1
6V2BC
11111,1 - 02.1112 - Σ
| 11.11170..n
s=1
lash (0h) --es la.h (Dit1.t)
C
+ 4AB
&
|1ā+tI, - -0,.0112 Σ + +6V2BC Σ
10 02.0112 "
am1
am1
where the last inequality holds by 11 0f S SA10ō,. finishes the proof.
0, < 4XB. Plugging Ç = 21
23

---

F.2 Proof of Lemma 2
Proof. According Lemma 11, we have
k
- Ce ((h(Or+1n))
110+11
07
2nn
(1,) -
+ 4AB
k
+ 12v2BB
Σ 10++1A
02n111
>
10 - 00
We bound the right-hand side of the above lemma separately in the following. The most challenging part is to bound the term Σ (0%)) Ei=1 (1, At first glance, this term appears straightforward to control, as can be observed that 0% arg mingead E.. (0) & Eyg, Le,, (0)), where the instantaneous loss fi (0) serves as empirical observation of &,. (0). Consequently, the loss gap term seemingly can be bounded using appropriate concentration results. However, caveat lies in the fact that the update of the estimator 0,- depends the information li more precisely Yi,h, making it difficult to directly apply such concentration results.
To address this issue, we decompose the loss gap into two components by introducing an intermediate exp([a])>
term. Specifically, define the softmax function as [=)), T+E exp[[=]]. Vs E Sk, Using this definition, the loss function can be rewritten as:
1 log
[ou.n
S'E
Define a pseudo-inverse function of (.) as 1 (p)]x = log |p]|| < 13. Then, the loss gap term can be decomposed into two parts follows.
Ip I
vp {p E [0, 1SA
(0,) Ca,t (1,((1+1n))
(11, (Z..
(en(zan V..)) - li (.++..)))))
tern (a)
born (b)
where 24,6 ox (Baw lo 0) ee Ph, & N( (1 cHr,,h) is the Gaussian distribution with mean Ok.h and covariance (1 (H,))) where is constant to be specified later.
The design of the intermediate term was originally proposed by Zhang and Sugiyama [2023] in their study of the multiclass logistic bandit problem and was subsequently applied to the multinomial logit bandits problem by Lee and Oh [2024]. Notably, the intermediate loss is independent of the information contained in yr.,, enabling the application of concentration results. Specifically, based on Lemma F.2 and Lemma F.3 of Lee and Oh [2024], we obtain the following upper bounds for them.
For term (a), let 8 (0, 1] and max 72ed), for all [K], h E [H], with probability least 1- 6, we have
term (a)
17
2H 1 2k
2H / 2h
)) + 2.
< (3log(1 + (U + 1)k) +3)
+ 2V
+ 16 log
16
6
For term (b), for all ls E [K] h E [H]. we have
term (b) S 2c
Σ
~
00. 8 8 Men
+ Voedlog
1
1: 1+1
2A
im1
24

---

Combining term (a) and term (b), we have
10s+1,1 0fl
17
2Hv14 + 2k
2/1 vI++ +1+++6266 26
< 2n (3 log( + (U + 1)k) +3)
- A + 2v
+ 16 log
16
6
5
-2 + Voodlog (1 1+ k k+11
+ 4XB 12 2Bn
01+1A
1 + ("'
-11 >
1 + 0i Mi,
21
i=1
i=1
17
2H 2k
2H v 1+ 2h
2n
(3 Blog(1 + (U + 1)k) 3)
A 2VAlog
+ 16 log
16
6
+2+ V6ed log [+ k *+1
4AB,
2A
where the second inequality holds by setting c= 7n/6 and X 2 max max 84dn), we have
k
12V2BB
00 I.A
10+11n + Ūz,n 114.. 112 + (" - Σ
1
12v2BB
10. 0i,111 7
11+1. + 1l Σ
i=1
(12V2BM
Σ
10+ -0,,1113
7
0..
Thus, by setting = 1 3 log(U + + (B+ 84 + d), we have
10k+16- - 07 S00ti....((00 CoVvdlogUlog(+1) & Br-
This finishes the proof.
E3
Proof of Lemma 3
Proof. Lemma follows directly by substituting the confidence set Cg,b defined in Lemma 2, into Lemma 7. This finishes the proof.
F4 Proof of Theorem 2
Proof.
Combining Lemma and Lemma 9, we have
K
H
Σ
(sk.1)
Σ V (sk.1) 2
Ckhh + and +k,h)
+ H 2K H/H2KH log(2/8)
where
1st k.h
HBs Σ
Ph (Bk.h) 1
Σ
e'ESu.h
""ESk.
5
k.
and
- H
2
| 11 S'S
max
Hzh
Next, bound Bounding kk For simplicity, denote
k,h and C respectively.
Eg (6 Egrop, (0) (dh'n)
Hz's =baa
F.
He. 15 E R 188.1
25

---

Then, we have
E O0 E
(0
E
thin (n 1ll
Hich
Σ
- @illlzent
E
Phin (0s,N) ohhn Il
S'ESa
Σ
Taillleeh +
(0 1
B'ESE,
(c)
(d)
(0+11
*ES
tarn (e)
We bound these terms separately in the following. For the first term (c), we have
Σ
(PE - PE (h(((E)))) oi I
A
Σ
(VRRN(ERNN) (OK+I1 - Fauh) 0i'1n Nil
Σ
(ERN)) (0K4IA - -Okial 11102inl
S"ESE,
Σ
(PET (EuN) Σ
(SRA)))) (0k+1nn- Taaaian-aaal 0a.n) 1 11
(EAN) (0R+1, Fman) S
Σ
(
Σ
(Sm ((6th (Ōx+1,0 ((0kt") 0m.nal
"ESKA
""EESLA
Σ
(ER.)) - Teuulleen Meleeallllffi I
S'ES
Σ
Σ
Pi, (GLW)) 10 Tk.ill
"EES
4n
An
Σ
Σ
+ Vx
""ESk.h
8n
Σ
"
81
max
where and the fourth inequality is because by Lemma 15 and the fact He, 2 Hk. 2 Ala, we have
211 [VEL,
1 - -m.allzu S 110eTLA 0R.n fl S 2n (l,, S
and since (0) ExVES,, (V) w we have
(eaal E Ph.non) -
Σ
2 max s'E
|| S 2.
S'ESu.
S'ESu.
26

---

Therefore, we have
H
ΣΣ Σ P 0k 1= S'
HEullussh
8n
Σ
max
s'ESu.h
H
8n
|
max ESrt
s'ESu.
16Hn
1+ K ax)
dlog
(23)
KVA
where the last inequality holds by Σ max
11 P S &d (1 Xed
*
in Lemma 6.
For the term (d), by similar analysis, we have
(Vi, (Fa.)) ph,, (+++1,,))) 0 AEEA
(ERA (0k, 0 11
= -SEENEENNEE PEL(EE) S"ESk.
E Phlalaaaohhn T (0k+In - Bkiw)ll Ilacz
4n (SAAA
11 1 + th (Ea,)) 10 Pe d'ESt.N
E
S
VX
4n
max
|1 112. 1 16 blii ESE
+ max
1 Painl,n
max ESk,
VX
21)
(10fialleEt +
-100%' (PPEE
max SAS
V
2m + Vx
(1
|| (1 )²
max E"E
+ ES
max
81
|oE Hi
11 2 ES
max
max ES....
1. max
where the third inequality holds by the AM-GM inequality. Thus, have
K
H
Σ
ph (0611)))) F (G.N)
hmm
S'E
K
H
8m
| N. 1
1 11 Pest
max
max s"ESu
max ESS
k=1 k=1 h=1
16 log
K
cl
1+
(24)
kVA
dd
where the last inequality holds by Σt max 1 S =ddog (1
x Xid
in Lemma 6.
Finally, we bound the term (c) as follows.
K
Σ
A=1
S
K (iinOOnL.N)
Σ
Σ
k= S'E
d'Se.n
1+ K dd
<
K
2dlog
(25)
27

---

where the first inequality holds by the Cauchy-Schwee inequality and the last holds by Lemma 6. Thus, combining (23), (24), and (25), have
k
K
H
HBK
ΣΣ
E
Σ
Ph
k,h
Hejh
A= 1=
k= =11=11m d'ESk.
s"ESua
(V
(1+
K
32n
K (1+
22KK log
1+
dloog
(26)
dA
KVA
di
For the second-order term, by Lemma 6, we have
K
H
K
H
and RRh
HIR
max 1
10 S 21 3x
1 di
(27)
2
S'E
A==1
1= h=1
where the last inequality holds by E maxves,, 1 H.Gh Combining (26) and (27), we have
S Ed 1+ Xed
in Lemma 6.
Reg(K) s
Cke + ck,h)
H (ogg22))(
k=1 h=1
V
2dk log
K 1+
32m
d log
1+ dx
K
))
+ B
dog
1+
K
di
H 2 log
S O(dH' + d d2222
This finishes the proof.
G Omitted Proofs for Section
G.1 Proof of Theorem
Proof. Our proof is similar to adversarial linear mixture MDPs with the unknown transition in Zhao al. [2023]. We prove this lemma by reducing MNL mixture MDPs to a sequence of logistic bandits.
We use each three layers to construct a block. Note that the third layer of block is also the first layer of block i and hence there total H/2 blocks. In each block, both the first and third layers of this block only have one state, and the second layer has two states. Here we take block as an example. The first two layers of this block are associated with transition probability PP,11 and IP,,2- Denote by 8, the only state in the first layer of this block. In the second layer the block i, we assume there exist two states si and 5;,2- Let 81,3 the only state the third layer of this block. Further, for any E A. let ((8i,1, 1 a, 81,2) 0. The transition probability is defined follows:
exp(ø(s(2) $1,1, Tor,) Pi a) 1 1+ cxp(((()) 81,1, a) TT T0 Pa: Pt, (8,1, Pa-
81,,, and a E A, (t,,3 s, = 1. The reward satisfies For the second layer, it satisties Vs S1,, r a) = 0 for the first layer and rı (x) a) = 1, rx (81,2, a) for the second for all E A.
Then, consider the logistic bandit problem where learner selects action r I and receives reward rą sampled from the Bernoulli distribution with mean p(x T8)) = (1 + cxp(x (*)) By this configuration, we can see that learning in each block of MDP can be regarded as learning d-dimensional logistic bandit problem with A arms, where the arm set is o(s 18,1, a) and the expected reward of each arm Pa- Thus, learning this MNL mixture MDP equals to learning H/2 logistic bandit problems. This finishes the proof.
28

---

H Supporting Lemmas
In this section, we provide several supporting lemmas used in the proofs of the main results.
Lemma 12 (Abbasi- Yadkori et al. [2011, Theorem 1)). Let {Fi)r=) be filtration. Let {nh )itz= be a real-valued stochastic process such that The is Fe-measurable and The conditionally zero-mean R-sub- R-sub-Gaussian for some R i.e. AA R, E [ Fi-1] exp (X² /2).222..2) Let (Xt)r=) be an Rd- -valued stochastic process such that Xt is Fim---uasuaalle Assume that V is d positive definite matrix. For any 2 1, define
t-1 V = Σ X,X_ S.
V
Σ Xx ==1
Then, for any d E (0, 1), with probability at least 1 for all tz 1,
|S V. S RV 2 log det (V,) del (V) -1/2
8
Lemma 13 (Périvier and Goyal [2022, Theorem 4)). Let {Fili be a filtration. Let {ōr be an R valued stochastic process such that 6e Fr F--massurable one-hot vector. Furthermore, assume B[ā,[Fe-1] = Pt and define process such that Xt is Fmmm-muauurable and [X S 1, [N]. Let (Mi be a sequence of non-negative scalars. Define
Pt dt. Let { (X))e be sequence of -d--vluedd stochastic
N 1I=EE X - ΣΣ j=1k=1
[-1
N N P.PaX..
t-1 N S.= ΣΣ Xt..
He ===E i=1
+ tNla
1=1
1=1
Then, for any ( E (0,1), with probability least 1 S. all 1,
||S H 1 15 Vx
det det. (H,) X,
Axr log
Lemma 14 (Abbasi- Yadkori et al. [2011. Lemma 10]). Suppose FI..... It E Rd and for any 8 I t, ||2,|l2 < L. Let Vg = Al. + E. N,T. for X 2 O. Then, we have det(Vi) S (X + tL' /d)
Lemma 15 (Orabona [2019, Lemma 6.91). Let Z be a positive define matrix and W be convex set, define W the solution of
W arg min { (g. w)
|ww wol1
wEW
27
Then we have
Wi+1 - wellz S 2n/1gl|z-1.
Lemma 16 (Campolongo and Orabona [2020, Proposition 4.1)). Define Wi+1 the solution of
Wi+1 arg min (n]((w)= + Do (w,we) }.
weV
where V C W C Id is non-empty convex set. Further supposing ((w) is -strongly convex w.r.f. a certain norm in W, then there exists ag! E de, (We+1) such that
(mgl,, We41 u) < (V (w:) Veb (We+1), W u)
for any W.
Lemma 17 (Lee and Oh [2024, Lemma D.3l). Define Q RRK + R, such that for any exp(us).
(u (u1,..., ug) "RRKQQQ Q(()) ΣK at EE explue)
exp(1:)
Let pu(
ut E+ exp(uz)) Then, for all
i [K]. we have
PQQ
(3)
fi==j,
0i0j
(p)p())
ii
29

---

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:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of this work in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
30

---

We present the assumption in Assumption 1 and provide detailed proofs for all theoretical results in the appendices.
Justification:
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 in the statement of any theorems.
The proof's 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 a 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 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 to 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 is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer:
[NA]
Justification:
This is a theoretical paper and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ public/guiden sonuiides/CoddSummisseese wwriiisssooolliooooooo icyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //iips.cooo wttpccccppppcpeeeecececccccccccc /ttp://///.ieeeeeeeeuuubiiiiiiii /Codeeeooiissseeeeee wwtpaubmmsssoonni ssisnnol onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is a theoretical paper and does not include experiments.
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 be 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: [NA]
Justification: This is theoretical paper and does not include experiments.
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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 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: : htt////eurrpp..// cc
Answer: [Yes]
Justification: This paper adheres fully the NeurIPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 is theoretical paper and there is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
33

---

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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretical paper and does release any data models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
34

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is theoretical paper and 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to the NeurlPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does 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.
35


Reviews:
[{"review_id": "FKyl2pwdfS", "reviewer": "Reviewer_qUhc", "summary": "The paper studies the recently proposed MDPs that use multinomial logit function approximation for state distribution validness. The results and algorithms improve the prior work of Hwang and Oh [2023] in multiple aspects, including computation efficiency, storage, and statistical dependence on the problem-dependent quantity $\\kappa$ that can be exponentially small. In addition, the authors establish a matching lower bound on $d$, the feature space dimension, and $K$, the number of episodes.", "questions": "Overall, I think the paper makes reasonable contributions to the problem, and I have no additional questions/comments besides the above.", "limitations": "The authors have made various comparisons and discussed the limitations of the results, which I'm satisfied with. I do not see any potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and has clear logic flows. Readers can see how the authors approach the MDP problem and tackle the challenges. In particular, Table 1 is quite useful for demonstrating the advancements in the work.\n- The improvements in both computation and storage efficiencies are essential for practical applications. In Theorem 2, the authors also improve the dependence on $kappa$ to $\\sqrt{\\kappa}$ without affecting efficiency. The enhancement seems significant, especially since the parameter can be exponentially small. \n- The lower bound established in the paper is the first to demonstrate the optimality of the authors' algorithms in the $d$-$K$ dependence. Per my understanding, it also confirms the results' optimality of Hwang and Oh [2023].", "weaknesses": "- The primary high-level techniques and tools (seem to) come from existing works and relevant fields, such as MNL contextual bandits. The authors should put more effort into highlighting the technical challenges and novelties besides the previous comparisons. \n- It would be beneficial to include experiments on synthetic and real-world datasets and compare the results to existing baselines and relevant works. In particular, the new algorithms seem more involved than prior ones, which may affect their stability and adaptiveness.\n- There is still a significant gap between the lower and upper bounds. Besides, I wonder how often $\\kappa$ could be exponentially small in practical settings, though it's definitely of theoretical interest to approach the lower limits on parameter dependency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review. We will address your concerns below.\n\n---\n\n**Q1:** \"The primary high-level techniques and tools (seem to) come from existing works and relevant fields...\"\n\n**A1:** While similar ideas have been explored in the bandit setting, there are several unique challenges specific to MDPs that need to be addressed, especially due to the concerns of the intrinsic dimension in RL with function approximation setting. Below, we highlight the key differences between our work and the existing literature:\n\n- **Compared with Zhang & Sugiyama (2023).** The model of Zhang & Sugiyama (2023) fundamentally differs from ours. We employ a *single-parameter* (i.e., a vector $\\theta_h^*$) model for different states at each stage $h$, whereas they use a *multi-parameter* model (i.e., a matrix $W_h^*$). As a result, the techniques in Zhang & Sugiyama (2023) cannot be directly applied to our setting because some key properties of the functions differ. For instance, a direct application of their method would result in a regret bound that scales linearly with the number of reachable states $U$. \n- **Compared with Lee and Oh (2024).** While Lee and Oh (2024) study the single-parameter MNL bandit setting, and our parameter update approach shares some similarities to theirs, their construction of the optimistic value function is significantly different. They use a first-order upper bound for each item, which is insufficient to remove the dependence on $\\kappa$ in our setting. To address this, we employ the second-order Taylor expansion to achieve a more accurate approximation of the value function. \n\nWe will emphasize the challenges and our contributions more clearly in the revised version.\n\n---\n\n**Q2:** \"It would be beneficial to include experiments on synthetic and real-world datasets...\"\n\n**A2:** Thanks for your suggestions! We agree that adding experiments would be beneficial to the work. Nevertheless, our primary goal is to enhance the theoretical understanding of RL function approximation rather than designing a specific algorithm with state-of-the-art empirical performance for MNL MDPs. More specifically, the main focus of our paper is to investigate *whether we can achieve (almost) the same computational and statistical efficiency as linear function approximation while employing a more expressive non-linear function approximation*. We answer this question affirmatively by considering the MNL MDPs, which broaden the scope of RL with function approximation. Therefore, to some extent, our focus is mainly on the theoretical aspect. Given that our current upper bounds still exhibit a gap compared to the lower bound (as discussed in the next question), we may have to focus on how to achieve the minimax optimal rate for now, which is definitely a challenging open problem to work with and leave the empirical evaluation as the future work.\n\n---\n\n**Q3:** \"There is still a significant gap between the lower and upper bounds.\"\n\n**A3:** There is indeed a gap between the lower and upper bounds, but may not be as significant as it seems. The lower bound we established is *instance-dependent*, and if we focus on the worst-case guarantee, the lower bound is $\\Omega(d H \\sqrt{K})$. Our upper bound only looses a factor of $H$ compared to the lower bound, which is acceptable. As we discussed in Line 306-314, closing this gap remains a challenging open problem, and we will add more discussion on this point in the revised version.\n\n---\n\n**Q4:** \"I wonder how often $\\kappa$ could be exponentially small...\"\n\n**A4:** Thanks for your insightful question. The phenomenon that $\\kappa$ is exponentially small is quite common in practice. As $\\kappa$ is defined as minimum value of the product of any two state transition probabilities (i.e., $\\inf_{\\theta \\in \\Theta} p_{s, a}^{s^{\\prime}}(\\theta) p_{s, a}^{s^{\\prime \\prime}}(\\theta) \\geq \\kappa$), it will be extremely small if there are some hard-to-reach states with very low transition probabilities. For example, in autonomous driving, there are emergency states that are rare and have very low transition probabilities. Similarly, in financial trading, sudden market crashes or booms are rare events that can be considered hard-to-reach states in the market conditions state space. These events typically occur under unusual conditions and are not frequently observed, resulting in low transition probabilities.\n\n---\n\nWe hope our responses address your concerns. We are happy to provide further clarification if needed. Thanks again for your valuable feedback.", "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": "b3DZaxmgWN", "reviewer": "Reviewer_zUWe", "summary": "The problem considered in this paper is online learning in MDPs where transition probabilities are modelled with a log-linear model (with \"multinomial logit function approximation\"). The finite horizon, time-inhomogenous setting is considered. The problem is motivated by allowing a nonlinear transformation in modeling the MDP and yet maintaining both computational and information theoretic tractability. Inspired by results in the analogous bandit problems and algorithms developed for them, a number of gradually more complex, but (statistically) better performing algorithms are considered. In particular, while naive approaches give a poor dependence on a problem parameter $\\kappa$ that characterizes the \"strength\" of nonlinearity, by adopting previous ideas to the MDP setting, new algorithms are designed that eliminate this poor dependence. A lower bound is also established, which nearly matches the upper bound (but considers infinite action spaces, while the main paper considers finite action spaces).", "questions": "1. Can you confirm that the regret and compute cost depend on U, the worst-case number of next states that one can transition to with positive probability? Do you think such dependencies are necessary? Are there any interesting examples where it is reasonable to expect that U is small, independently of the size of the state space?\n2. What was the most challenging aspect of extending the bandit ideas to the MDP framework?", "limitations": "n.a.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a reasonable problem setting; and the approach is also reasonable. It is nice to have a lower bound, even if there is a mismatch between the settings. It is nice to see that ideas that were developed for the bandit setting generalize to the MDP setting.", "weaknesses": "1. The novelty is limited by that we have seen the same story, same ideas playing out nicely in the closely related bandit setting. \n2. A new parameter, U, the number of next states that are reachable with positive probability in the worst case, appears in the analysis and will appear in the bounds.\n3. It is an unpleasant surprise for the reader to discover this dependence only through carefully reading the paper, rather than being told upfront. It is not good that the opportunity to discuss whether this quantity needs to enter the regret bound, and that this quantity needs to be small for the algorithm to be tractable, is missed.\n4. Line 83 and onward: The work of Uohamma is discussed but is mischaracterized. My reading of this work is that they do establish that their algorithm runs in polynomial time. It remains unclear why the exponential family model is incomparable with the one considered here; an explanation (with examples) is missing.\n5. The paper could use some extra proofreading (e.g., the upper indices in the bottom of page 5, in the displayed equation are not correct); in line 149, in the definition of $U$, $|\\cdot|$ is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review. Below, we will address your main questions, especially regarding the dependence on $U$ (see A1-a,b,c), technical challenges (see A2), the difference to prior work (see A3), and presentation issues (see A4).\n\n---\n\n**Q1-a:** \"The regret and compute cost depend on $U$?....  Do you think such dependencies are necessary? \" \n\n**A1-a:** We appreciate your observation. Though $\\kappa$ may have polynomial dependence on $U$ in the worst case, the leading term of our best result (Theorem 3) is independent of $\\kappa$ and only has a logarithmic dependence on $U$. While the lower-order terms do depend on $\\kappa$, they are independent of the number of episodes $K$ and can be treated as constants. Thus, this dependence is believed to be acceptable. The dependence on $U$ is necessary for our method and we explain the reasons below.\n\nIn general, methods for MDPs can be classified into two categories: model-based and model-free. Model-based methods aim to maximize the likelihood of observed data while model-free methods focus on minimizing the mean-squared error in predicting value functions. \n- The dependence on $U$ for regret and computational cost is usually necessary for the model-based methods, as it controls the model's error, which typically involves a total of $U$ elements. Similar dependencies have been observed in the literature (e.g., Hwang & Oh, 2023). \n- Most papers on linear MDPs use the value-targeted approach, a model-free method that does not rely on such dependencies. This is feasible because the linearity of the value function in linear MDPs allows for learning the value function directly. In contrast, **the value function for MNL-MDPs is neither linear nor log-linear**, preventing using model-free methods. \n\nWe will further elaborate on this point in the revised version.\n\n---\n\n**Q1-b:** \"Examples where $U$ is small...?\"\n\n**A1-b:** This phenomenon is quite common in practice, as in many applications, the agent tends to transit to nearby states even if the entire state space is large. An illustrative example is the RiverSwim environment in Hwang & Oh (2023), where although the state space is extensive, the agent only transits to adjacent states. Another example is the SuperMario game, where, despite a vast state space, the value of $U$ is limited to 4, corresponding to the possible movements: up, down, left, or right.\n\n---\n\n**Q1-c:** \"It is an unpleasant surprise for the reader to discover this dependence...\"\n\n**A1-c**: Thanks for your helpful suggestion. We will discuss this dependence in the next version.\n\n---\n\n**Q2:** \"The novelty is limited... What was the most challenging aspect...?\"\n\n**A2**: While similar ideas have been explored in the bandit setting, there are several unique challenges specific to MDPs that need to be addressed, especially due to the concerns of the intrinsic dimension in RL with function approximation setting. \n\n- **Compared with Zhang & Sugiyama (2023).** The model of Zhang & Sugiyama (2023) fundamentally differs from ours. We employ a *single-parameter* (i.e., a vector $\\theta_h^*$) model for different states at each stage $h$, whereas they use a *multi-parameter* model (i.e., a matrix $W_h^*$). As a result, the techniques in Zhang & Sugiyama (2023) cannot be directly applied to our setting because some key properties of the functions differ. For instance, a direct application of their method would result in a regret bound that scales linearly with the number of reachable states $U$. \n- **Compared with Lee and Oh (2024).** While Lee and Oh (2024) study the single-parameter MNL bandit setting, and our parameter update approach shares some similarities to theirs, their construction of the optimistic value function is significantly different. They use a first-order upper bound for each item, which is insufficient to remove the dependence on $\\kappa$ in our setting. To address this, we employ the second-order Taylor expansion to achieve a more accurate approximation of the value function. \n\nWe will emphasize the challenges and our contributions more clearly in the next version.\n\n---\n\n**Q3:** \"The work of Ouhamma et al. (2023) and why it is incomparable..\"\n\n**A3:** Thanks for pointing it out. Ouhamma et al. (2023) studied the exponential family model, a similar setting to ours. However, our work exhibits differences from theirs for both problem setting and computational complexity. Below, we make the clarifications.\n\n- **Problem setting.** The MNL MDPs studied in this paper can not be covered by the exponential family of MDPs in Ouhamma et al. (2023). An example of an MNL MDP that does not belong to the exponential family is given by the function $\\phi_i(s, a, s') = \\exp((s' - s -i)^/a^2) / \\sqrt{\\pi a^2}$. It does not belong to the exponential family as $\\phi_i(s, a, s')$ can not be decomposed in the form $\\phi_i(s, a) \\cdot \\psi_i(s')$. More discussion on this point can be found in Zhou et al. (2021).\n- **Computational complexity.** Though the algorithm of Ouhamma et al. (2023) runs in pseudo-polynomial time, our method is more efficient regarding storage and computational complexity. They estimate the transition parameters using the maximum likelihood estimation (MLE), which requires storing all previously observed data. Consequently, the computational complexity at episode $k$ is $O(k)$. In contrast, we employ an online parameter update method, which requires only $O(1)$ storage and computational complexity per episode. \n\nWe will provide a more detailed comparison in the next version.\n\n---\n\n**Q4:** \"The paper could use some extra proofreading\"\n\n**A4:** We appreciate your feedback and will ensure that the revised version is thoroughly proofread.\n\n---\n\nWe hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.\n\n---\n\n**Reference:**\n\n[1] Zhou, D., He, J., & Gu, Q., Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping. In ICML'21.", "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": "kJTFmaWugn", "reviewer": "Reviewer_xBZM", "summary": "This work studies the MNL function approximation inhomogeneous RL, achieves the $O(1)$ computation cost, and improves the regret guarantee with regard to $\\kappa$. To improve the computation cost, this work employs the online Newton step instead of MLE estimation to estimate $\\theta$. Then, they design a novel confidence set by making full use of local information to improve the dependence of $\\kappa$.", "questions": "Question 1: This work achieves great results in the stochastic reward setting. Can you discuss the challenge when extending to the adversarial reward setting?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe use of local information instead of a uniform $\\kappa$ is novel and useful to improve the dependence of $\\kappa$.\n2.\tThe UCRL-MNL-LL+ removes the $\\kappa$ dependence on the lower-order term and almost matches the optimal regret results by using high-order Taylor expansion.", "weaknesses": "1.\t[1] also use the online Newton step to improve the computation cost in the logit contextual bandits setting. It would be better to discuss the novelty of UCRL-MNL-OL.\n\n[1] Oh, M. H., & Iyengar, G. (2021, May). Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 10, pp. 9205-9213).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful review. We will address your questions below.\n\n---\n\n**Q1:** \"Oh & Iyengar (2021) also use the ONS to improve the computation cost...\"\n\n**A1:** As mentioned in Line 184, the parameter estimation of UCRL-MNL-OL algorithm is inspired by the work of Oh & Iyengar (2021). However, to construct the optimistic value function efficiently in MNL-MDPs, we had to develop a different approach tailored to the specific structure of the value function in MNL-MDPs. Moreover, as highlighted in Remark 1 of our paper, we identify and address a technical issue present in their work.\n\n---\n\n**Q2:** \"Can you discuss the challenge when extending to the adversarial reward setting?\"\n\n**A2:** Thanks for your insightful question. Extending our method to the adversarial reward in the full-information setting is relatively straightforward. Instead of using a greedy policy (i.e., $a = \\mathrm{argmax}~ Q_k(s, \\cdot)$) as in our current approach, we can incorporate a policy optimization step, such as $\\pi_{k+1}(\\cdot | s) = \\pi_k(\\cdot | s) \\exp(\\eta Q_k(s, \\cdot))$. This modification would result in an additional regret term of $O(H^2 \\sqrt{K})$. However, extending our method to the adversarial reward setting for the bandit setting is more challenging, as we need to handle both unknown transitions and unknown rewards simultaneously. To the best of our knowledge, even the state-of-the-art algorithms for linear mixture MDPs in this setting of Li et al. (2024) exhibit a regret bound that scales linearly with the number of states.\n\n---\n\nWe hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.\n\n---\n\n**Reference:**\n\n[1] Li, L. F., Zhao, P., & Zhou, Z. H., Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition. In AISTATS'24.", "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": "GNigoQy4yk", "reviewer": "Reviewer_Roix", "summary": "In this paper, the author analyzes a Markov Decision Process (MDP) model with non-linear function approximation. Specifically, in the finite-time horizon inhomogeneous episodic MDPs setting, the transition dynamics are unknown but the reward function is known. The author proposes using a multinomial logit (MNL) function approximation to estimate transition dynamics, which is superior to the linear function approximation if the model is misspecified in \\cite{hwang2023model}. Additionally, the author proposes *UCRL-MBL-OL*, which adapts the previous work that is model-based and has large computational and storage complexity, to an online style that only consumes constant computation and storage resources. Moreover, the author has proven that the regret bound of *UCRL-MBL-OL* matches the state-of-the-art in Theorem 1. Its regret bound achieves $\\tilde{O}(\\kappa^{-1} dH^2\\sqrt{K})$, where $H$ is the time horizon length, $K$ is the number of total episodes and $\\kappa$ is considered as a parameter to control the sparsity of the transition dynamics and $d$ is the hidden dimensionality. Ignoring the logarithmic factor and $\\kappa$, such a regret bound has only a $\\sqrt{H}$ gap compared to the lower bound. After that, with additional assumption, the author utilizes the local information to propose another two algorithms, *UCRL-MNL-LL* and *UCRL-MNL-LL+* to remove the dependence on $\\kappa$ and get a tighter regret bound as well as maintain good properties of *UCRL-MNL-OL*.", "questions": "Please see the above \"Weaknesses\"", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written. The author makes a clear improvement point compared to the literature.\n\n2. The algorithm proposed by the author enjoys an online learning style that does not need to maintain a large historical set.", "weaknesses": "1. Although this paper focuses on reducing the computation complexity, I am curious about the sample complexity of *UCRL-MNL-OL*.\n    \n2. Since the algorithm builds up the estimation of the transition dynamics by using MNL function approximation, is it considered a model-based algorithm? More specifically, does it require storing the transition dynamics for each state-action pair in every step?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback. We will address your questions below.\n\n---\n\n**Q1:** \"Although this paper focuses on reducing the computation complexity, I am curious about the sample complexity of UCRL-MNL-OL.\"\n\n**A1:** Thanks for your question. This work not only reduces computational complexity but also significantly improves sample complexity. A sample complexity guarantee can be derived from any low-regret algorithm using an online-to-batch conversion, as demonstrated by Jin et al. (2019). Specifically, suppose we have total regret $\\sum_{k=1}^K[V_1^{\\star}(s_1)-V_1^{\\pi_k}(s_1)] \\leq \\sqrt{CK}$, then, randomly selecting $\\pi = \\pi_k$ we have that $[V_1^{\\star}(s_1)-V_1^{\\pi}(s_1)] \\leq \\sqrt{C/K}$ with constant probability by Markov's inequality. Thus, Theorem 1 implies UCRL-MNL-OL has a sample complexity of $O(\\kappa^{-1} d H^2 / \\epsilon^2)$. We will add this discussion to the revised version.\n\n---\n\n**Q2:** \"Is it considered a model-based algorithm? Does it require storing the transition dynamics for each state-action pair in every step?\"\n\n**A2:** Our algorithm is model-based because it first estimates the transition parameters and then derives the value function based on these parameters. However, unlike traditional model-based methods, it does not require storing the transition dynamics for each state-action pair at every step. Instead, we only store the estimated transition parameter (d-dimension vector) and compute the transitions at the current state as needed. This efficiency is achieved by updating the parameters in an online manner, eliminating the need to store the entire history of transitions.\n\n---\n\nWe hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.\n\n---\n**References:**\n\n[1] Jin, C., Allen-Zhu, Z., Bubeck, S. & Jordan, I. M., Is Q-learning provably efficient? In NeurIPS'18.", "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": "riOWsaWvoD", "reviewer": "Reviewer_tHPh", "summary": "This paper considers MDPs employing the MNL function for transition probability, following Hwang and Oh [2023]. The authors suggest efficient algorithms based on online Newton steps, inspired by [Hazan et al., 2014; Zhang et al., 2016; Oh and Iyengar, 2021]. Furthermore, to improve $\\kappa$ dependency, they provide algorithms employing local learning with mirror descent inspired by [Zhang and Sugiyama, 2023; Lee and Oh, 2024]. The algorithms achieve $1/\\sqrt{\\kappa}$ or even detach the dependency of $\\kappa$ from the leading term.", "questions": "Are there any non-trivial technical novelties in utilizing the online mirror descent method for MDPs?", "limitations": "The authors discuss some interesting future work regarding regret bound. Additionally, I believe, as mentioned in Weaknesses, the MNL model for transition probability has an inherent weakness: the number of achievable states for each (k,n) must be finite, and it is required to know the state space of $S_{k,n}$.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The suggested algorithms are computationally efficient and show improvement in $\\kappa$ compared to the previous work of Hwang and Oh [2023].", "weaknesses": "- Their suggested algorithms do not seem novel because they are based on previously proposed methods for logistic or MNL bandits. Specifically, the online Newton update is widely studied for MNL or logistic bandits [Oh and Iyengar, 2021; Zhang and Sugiyama, 2023].\n\n- Furthermore, the improvement on $\\kappa$ is based on the mirror descent algorithm proposed in [Zhang and Sugiyama, 2023; Lee and Oh, 2024], and the proofs seem to follow the steps in [Zhang and Sugiyama, 2023; Lee and Oh, 2024] in the appendix.\n\n- Lastly, the MNL model for transition probability may have an inherent weakness: the number of achievable states for each (k,n) must be finite, and it is required to know the state space of $S_{k,n}$.\n\n[1] Faury, Louis, et al. \"Jointly efficient and optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comment. We will address your questions and clarify any misunderstandings, which may be due to our inadequate emphasis on the technical contributions in the presentation. We will improve the clarity in the revised version.\n\n---\n\n**Q1:** \"Their suggested algorithms do not seem novel because they are based on previously proposed methods for logistic or MNL bandits... \"\n\n**A1:** We respectively disagree with this claim. While the idea of online updates has been utilized in previous works, we make several novel contributions in the MDP setting:\n\n- Oh & Iyengar (2021) use the global information of the Hessian matrix, which fails to remove the dependence on $\\kappa$. Moreover, we identify and address a technical issue present in their work as discussed in Remark 1, which is valuable to the community. \n- Zhang & Sugiyama (2023) consider a *multi-parameter* model (i.e., the unknown parameter is a matrix $W_h^\\star$), which differs fundamentally from our *single-parameter* model (i.e., the unknown parameter is a vector $\\theta_h^\\star$). The techniques in Zhang & Sugiyama (2023) cannot be directly applied to our setting because some key properties of the functions differ. For instance, a direct application of their method would result in a regret bound that scales linearly with the number of reachable states. \n- Lastly, we establish the first lower bound for this problem, which is a novel technical contribution.\n\nTo summarize, our paper presents *novel* algorithms and regret guarantees for RL with multinominal logit function approximation, and also contributes *novel* technical ingredients to achieve desired results.\n\n---\n\n**Q2:** \"The improvement on $\\kappa$ is based on the mirror descent algorithm proposed in [Zhang & Sugiyama, 2023; Lee & Oh, 2024]. Are there any non-trivial technical novelties?\"\n\n**A2:** While our work builds upon these two important prior works, our solution incorporates non-trivial technical innovations crucial for achieving favorable regret bounds, especially due to the concerns of the intrinsic dimension in RL with function approximation setting. Below, we highlight the technical novelties: \n\n- **Compared with Zhang & Sugiyama (2023).** As discussed in A1, Zhang & Sugiyama (2023) consider a *multi-parameter* model, which differs fundamentally from our *single-parameter* model. As a result, the techniques in Zhang & Sugiyama (2023) cannot be directly applied to our setting because some key properties of the functions differ.  A naive application of their method would lead to a regret bound that scales linearly with the number of the reachable states $U$. \n- **Compared with Lee & Oh (2024).** Lee & Oh (2024) study the single-parameter MNL bandit setting, and while our parameter update approach shares similarities with theirs, our construction of the optimistic value function differs significantly. Specifically, they use a first-order upper bound for each item, which is insufficient to remove the dependence on $\\kappa$ in our setting. In contrast, we employ the second-order Taylor expansion to achieve a more accurate approximation of the value function. This approach is non-trivial and requires a different analysis.\n\nWe will emphasize these technical novelties compared to prior works more clearly in the revised version.\n\n---\n\n**Q3:** \"The MNL model for transition probability may have an inherent weakness... \"\n\n**A3:** It is a mild condition that the reachable state space is finite and known to the learner, which has been used in prior works. Below we illustrate the reasons:\n\n- This condition holds for many practical applications, such as the SuperMario game, where, despite the vast state space, the reachable state space is limited to four states and known to the learner, corresponding to the agent's possible movements: up, down, left, or right.\n- In fact, even for linear mixture MDPs, which are extensively studied in the literature (Zhou et al., 2021; He et al., 2022), the standard assumption is that $\\sum_{s'} \\psi(s') V(s')$ can be evaluated by an Oracle. This assumption assumes that the state space is finite and known to the learner implicitly. Moreover, several works on linear mixture MDPs have regret bounds that depend on the size of the state space (e.g., Zhao et al., 2023; Ji et al., 2024). This also implies that the state space is finite. \n- Moreover, even without exact information of $S_{k,h}$, our results also hold when replacing it with its upper bound. \n\nImportantly, the MNL model ensures valid distributions over states, addressing the limitations of linear function approximation. We believe this is a key shining feature of the MNL model, which will take an important step towards bridging the gap between theory and practice.\n\n----\n\nWe hope the above responses sufficiently address your concerns. If our responses have properly resolved the issues raised, we would appreciate it if you could consider re-evaluating our work. We're also happy to provide further clarifications to additional questions.\n\n---\n\n**References:**\n\n[1] Zhou, D., Gu, Q., & Szepesvari, C., Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. In COLT'21.\n\n[2] He J., Zhou D., & Gu Q., Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. In AISTATS'22.\n\n[3] Zhao, C., Yang, R., Wang, B., & Li, S., Learning Adversarial Linear Mixture Markov Decision Processes with Bandit Feedback and Unknown Transition. In ICLR'23.\n\n[4] Ji, K., Zhao, Q., He, J., Zhang, W., & Gu, Q., Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs. In ICLR'24.", "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:

Meta-review: This work makes multiple contributions on bounding the regret in the recently introduced problem of reinforcement learning where the transition kernel is modeled as a multinomial logit. On the positive side, a first result obtains the same regret as an earlier result of Hwang and Oh but with much better efficiency in terms of space and computation. A next result greatly reduces the order of dependence on a commonly appearing, often very small problem-dependent constant ($\kappa$). A third result entirely avoids dependence on $\kappa$ in the leading term although paying linearly in $\kappa^{-1}$ in a non-leading term. Also, a lower bound from a somewhat related setting (but not identical, as the lower bound considers a setting with infinite action space) suggests the authors’ results are nearly optimal.

From a technical standpoint, this work seems to be reasonably strong (maybe not very strong, but in light of the contributions, it seems nice).

Another positive point which I only got from closely looking at the paper is that the authors identify technical issues in previous analyses and explain how to fix them. This is nice.

With the above said, there are some strong reservations about this work which should be very well addressed in the next revision:
- First, the regret bounds depend on $U$, the maximum number of reachable states. This dependence was not made clear in the presentations in the theorems in the main text, and the paper lacked discussion about this new dependence. In the discussion period, the authors argued that in many situations, $\kappa$ may already have some dependence on $U$. However, being up front about dependencies on problem-dependent constants, and discussing them, is very important.
- The authors’ work requires knowing the support of the next-state distribution. From the author discussion period, the examples provided by the authors to justify having knowledge of the support were not that convincing.

Overall, this is a worthwhile paper that would fit well in the conference proceedings. Despite the reservations stated above, I believe the paper should be accepted.
Decision: Accept (poster)