Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation

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.

Q1: "Their suggested algorithms do not seem novel because they are based on previously proposed methods for logistic or MNL bandits... "

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:

• 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.
• 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.
• Lastly, we establish the first lower bound for this problem, which is a novel technical contribution.

To 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.

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?"

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:

• 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$.
• 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.

We will emphasize these technical novelties compared to prior works more clearly in the revised version.

Q3: "The MNL model for transition probability may have an inherent weakness... "

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:

• 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.
• 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.
• Moreover, even without exact information of $S_{k,h}$, our results also hold when replacing it with its upper bound.

Importantly, 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.

We 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.

References:

[1] Zhou, D., Gu, Q., & Szepesvari, C., Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. In COLT'21.

[2] He J., Zhou D., & Gu Q., Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. In AISTATS'22.

[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.

[4] Ji, K., Zhao, Q., He, J., Zhang, W., & Gu, Q., Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs. In ICLR'24.

Overall, I agree that there are several adjustments needed to apply the mirror descent approach to RL. This work extends previous research on bandits to the RL setting. However, I have concerns about the significance of the technical novelty of this work. I believe that the second-order Taylor expansion mentioned by the author may not be unique to RL, as it is also used in bandit problems. Therefore, I'm maintaining my score.

Thank you for your helpful feedback. We will address your questions below.

Q1: "Although this paper focuses on reducing the computation complexity, I am curious about the sample complexity of UCRL-MNL-OL."

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.

Q2: "Is it considered a model-based algorithm? Does it require storing the transition dynamics for each state-action pair in every step?"

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.

We hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.

References:

[1] Jin, C., Allen-Zhu, Z., Bubeck, S. & Jordan, I. M., Is Q-learning provably efficient? In NeurIPS'18.

Thanks for your insightful review. We will address your questions below.

Q1: "Oh & Iyengar (2021) also use the ONS to improve the computation cost..."

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.

Q2: "Can you discuss the challenge when extending to the adversarial reward setting?"

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.

We hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.

Reference:

[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.

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).

Q1-a: "The regret and compute cost depend on $U$?.... Do you think such dependencies are necessary? "

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.

In 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.

• 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).
• 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.

We will further elaborate on this point in the revised version.

Q1-b: "Examples where $U$ is small...?"

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.

Q1-c: "It is an unpleasant surprise for the reader to discover this dependence..."

A1-c: Thanks for your helpful suggestion. We will discuss this dependence in the next version.

Q2: "The novelty is limited... What was the most challenging aspect...?"

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.

• 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$.
• 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.

We will emphasize the challenges and our contributions more clearly in the next version.

Q3: "The work of Ouhamma et al. (2023) and why it is incomparable.."

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.

• 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).
• 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.

We will provide a more detailed comparison in the next version.

Q4: "The paper could use some extra proofreading"

A4: We appreciate your feedback and will ensure that the revised version is thoroughly proofread.

We hope that our responses have addressed your concerns. We will be happy to provide further clarification if needed.

Reference:

[1] Zhou, D., He, J., & Gu, Q., Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping. In ICML'21.

Thanks for the rebuttal; it was useful. Overall, my feelings towards the paper have not changed: This is a fine peace of work that should get published. I still have some reservations concerning the model; in fact, one of the reservations I have I forgot to include into my original review is that the algorithm needs to know the support of the next state distribution. This combined with that the size of this support appears in the bound, and that in the related linear kernel MDP setting, the size of the support does not appear in the bounds makes me feel uneasy about the paper. Why is knowing the support problematic? Well, if the size of the support was not part of the bound, one could just "max out" the support (all states are possible next states). If not, in the lack of results showing that the algorithm is robust in the face of misspecified next state support, one is afraid that knowing the support will actually be important. And I expect knowing the support is kinda tricky. Consider for example the SuperMario game, mentioned in the rebuttal. Here, knowing the next states (all 4 of them) encodes a tremendous amount of information about the game. Just consider how many states there are here and compare this to the number 4. How realistic is that one would actually know the support in scenarios like this. So I have doubts. I think an example, where the assumptions are more natural would tremendously help the paper. Also, why not think of some "real" application that people may care about (I have to say I have a hard time imagining anyone to seriously care about how to play SuperMario; and I also have a hard time imagining a more general problem that has the characteristics of SuperMario (ie I don't have a problem with simplified examples, but SuperMario and other games just feel like too arbitrary and unrelated to any "real world" applications).) In summary, notwithstanding these reservations, I am in support of accepting the paper, given that it looks at a somewhat reasonable setting and makes a nontrivial contribution.

Thanks for your constructive review. We will address your concerns below.

Q1: "The primary high-level techniques and tools (seem to) come from existing works and relevant fields..."

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:

• 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$.
• 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.

We will emphasize the challenges and our contributions more clearly in the revised version.

Q2: "It would be beneficial to include experiments on synthetic and real-world datasets..."

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.

Q3: "There is still a significant gap between the lower and upper bounds."

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.

Q4: "I wonder how often $\kappa$ could be exponentially small..."

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.

We hope our responses address your concerns. We are happy to provide further clarification if needed. Thanks again for your valuable feedback.