Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

• URL: http://arxiv.org/abs/2405.20165v1
• Date: Thu, 30 May 2024 15:39:19 GMT
• Title: Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
• Authors: Wooseong Cho, Taehyun Hwang, Joongkyu Lee, Min-hwan Oh,
• Abstract summary: We study reinforcement learning with multinomial logistic (MNL) function approximation. We propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. Numerical experiments demonstrate the superior performance of the proposed algorithms.
• Score: 8.274693573069442
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study reinforcement learning with multinomial logistic (MNL) function approximation where the underlying transition probability kernel of the Markov decision processes (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, $\texttt{RRL-MNL}$, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency and establish that $\texttt{RRL-MNL}$ is both statistically and computationally efficient, achieving a $\tilde{O}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T})$ frequentist regret bound with constant-time computational cost per episode. Here, $d$ is the dimension of the transition core, $H$ is the horizon length, $T$ is the total number of steps, and $\kappa$ is a problem-dependent constant. Despite the simplicity and practicality of $\texttt{RRL-MNL}$, its regret bound scales with $\kappa^{-1}$, which is potentially large in the worst case. To improve the dependence on $\kappa^{-1}$, we propose $\texttt{ORRL-MNL}$, which estimates the value function using local gradient information of the MNL transition model. We show that its frequentist regret bound is $\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2)$. To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve both computational and statistical efficiency. Numerical experiments demonstrate the superior performance of the proposed algorithms.

Related papers

• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. introducing the non-linear function raises significant challenges in both computational and statistical efficiency. We propose an algorithm that achieves the same regret with only $mathcalO(1)$ cost.
  arXiv  Detail & Related papers  (2024-05-27T11:31:54Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  We study the statistical limits of Imitation Learning in episodic Markov Decision Processes (MDPs) with a state space $mathcalS$. We establish an upper bound $O(|mathcalS|H3/2/N)$ for the suboptimality using the Mimic-MD algorithm in Rajaraman et al ( 2020) We show the minimax suboptimality grows as $Omega( H3/2/N)$ when $mathcalS|geq 3$ while the unknown-transition setting suffers from a larger sharp rate
  arXiv  Detail & Related papers  (2021-02-25T15:50:19Z)
• Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
  We study exploration using randomized value functions in Thompson Sampling (TS)-like algorithms in reinforcement learning. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case $widetildeOleft(HsqrtSATright)$ regret bound for episodic time-inhomogeneous Decision Process.
  arXiv  Detail & Related papers  (2021-02-19T01:42:50Z)
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
  We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL) In this paper, we introduce an optimistically-perturbed variant of the popular randomized least-squares value (RLSVI) Under the assumption that the Markov decision process has low-rank transition dynamics, we prove that the frequentist regret of RLSVI is upper-bounded by $widetilde O(d2 H2 sqrtT)$ where $ d $ are the feature dimension, $ H $ is the horizon, and $ T $ is the total number of
  arXiv  Detail & Related papers  (2019-11-01T19:48:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.