Learning Kernel-Based MDPs from Episodic Preferential Feedback

Technical Summary: Learning Kernel-Based MDPs from Episodic Preferential Feedback

Problem Formulation
This work addresses the problem of Reinforcement Learning from Human Feedback (RLHF) within the setting of episodic Markov Decision Processes (MDPs). Unlike standard RL where agents receive scalar rewards, the learner here receives only binary preferential feedback. In each episode $k$, the learner deploys two policies, $\pi$ and $\pi'$, from a common start state to generate two trajectories, $\tau_k$ and $\tau'_k$. The feedback consists of a single binary label $y_k \in \{0, 1\}$ indicating which trajectory is preferred. This preference is modeled via a Bradley–Terry–Luce (BTL) link function applied to the difference of cumulative (unobserved) rewards:
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
where $\sigma$ is the sigmoid function. The goal is to learn a policy that maximizes the value function $V^\pi_1$ while minimizing cumulative regret, defined as the difference between the optimal value and the average value of the deployed policies.

The setting assumes a Kernel MDP structure, where the reward function $r_h$ and the transition operator $P_h$ are elements of a Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_k$ induced by a known kernel $k$. Specifically, the authors focus on the Matérn kernel family, which captures nonlinear structures and is norm-equivalent to Sobolev spaces, offering a generalization beyond linear MDPs.

Methodology: PROSTO Algorithm
The authors propose PROSTO (Preference based Regularized Optimization via Sampled Trajectory induced Optimism). The algorithm operates in episodes and utilizes a value iteration approach adapted for preference feedback and kernel function approximation.

1. Reward Estimation via Regularized Kernel Logistic Regression (KLRR):
   Since feedback is trajectory-level and binary, the reward vector $\theta$ is estimated using maximum likelihood estimation with a norm-weighted penalty. The estimator $\hat{\theta}_k$ minimizes the negative log-likelihood of the observed preferences plus a regularization term $\tau \|\theta\|^2_{\mathcal{H}_k}$. The covariates for this regression are the trajectory difference features $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. Exploration via Randomized GP Perturbation:
   To ensure sufficient exploration at the trajectory level without knowing the transition dynamics in advance (which prevents deterministic elliptic bonuses), PROSTO employs randomized exploration. An exploration noise vector $\epsilon_k$ is sampled from a Gaussian Process (GP) with a covariance structure dependent on the empirical covariance of trajectory differences. This noise is added to the reward estimate to induce optimism.

3. Value Function Estimation via Kernel Ridge Regression (KRR):
   The value function is estimated recursively. The next-state expected value is approximated using standard kernel ridge regression on transition samples. The final Q-function estimate $\hat{Q}^k_h$ combines the reward estimate (KLRR + GP noise) and the transition estimate (KRR), subject to clipping to ensure boundedness.

4. Policy Execution:
   The learner selects two policies, $\pi$ and $\pi'$, which are greedy with respect to their respective optimistic Q-function estimates. These policies are executed to generate the next episode's trajectories and preference feedback.

Key Technical Contributions and Challenges
The paper identifies three primary technical challenges specific to combining kernel MDPs with trajectory-level preference feedback and provides novel solutions:

• Controlling Log-Covering Numbers: In kernel MDPs, the log-covering number of the value function class scales polynomially with the inverse of the covering mesh $\epsilon$ and depends on the RKHS norms of the estimators. Unlike linear MDPs, where covering numbers are logarithmic in the episode count, kernel settings can lead to regret bounds that are vacuous if the estimator norms grow too large.

  • Solution: The authors carefully tune the regularization parameter $\tau$ in the KLRR to explicitly control the RKHS norm of the reward estimator. This keeps the covering number of the induced function class small, enabling meaningful confidence bounds.

• Trajectory-Level Exploration with Non-Smooth Noise: Standard exploration bonuses (elliptic bonuses) require knowledge of the full trajectory, which is unavailable at decision time. Randomized exploration via GP sampling is used, but GP sample paths from a Matérn kernel generally do not belong to the corresponding RKHS (they are less smooth). This renders standard covering bounds inapplicable.

  • Solution: The authors derive new high-probability Gaussian covering bounds for the posterior GP sample paths. They leverage results from van der Vaart and van Zanten [2008] to show that while GP paths lie outside the RKHS ball, they lie within an $\epsilon$-neighborhood (in $\ell_\infty$ norm) of a suitably enlarged RKHS ball with high probability. This allows for the derivation of covering bounds necessary for the regret analysis.

• Balancing Regularization and Covering Parameters: Tuning the regularization parameters ($\tau$ for reward, $\lambda$ for transition) and the covering mesh $\epsilon$ is non-trivial. A small $\epsilon$ reduces misspecification error but inflates the covering number; a large $\epsilon$ does the opposite.

  • Solution: The authors jointly optimize $\tau$, $\lambda$, and $\epsilon$ as functions of the number of episodes $K$ and the kernel smoothness parameter $\beta_p$. This balancing act ensures that the confidence widths remain tight enough for sublinear regret while controlling the complexity of the function class.

Results and Regret Bounds
The paper proves that PROSTO achieves a sublinear cumulative regret bound for all kernels in the Matérn family. Specifically, the regret $R(K)$ scales as:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
where $\beta_p > 1$ is the eigen-decay parameter of the kernel, $H$ is the horizon, and $\kappa_Z$ is the maximum inverse link gradient. The exponent of $K$ is strictly less than 1, implying convergence to the optimal policy as $K \to \infty$.

Furthermore, the algorithm is computationally efficient, with a runtime polynomial in the number of episodes $K$. This distinguishes it from prior works on kernel MDPs with standard rewards (e.g., Maran et al. [2024b]) which, while achieving sublinear regret, rely on domain partitioning or optimization oracles that are not known to be computationally tractable in polynomial time for general kernel settings.

Significance and Claims
The authors claim this work provides the first algorithm for preference-based RL in kernel MDPs that achieves provable sublinear regret for the entire Matérn kernel family while being computationally efficient.

• Theoretical Novelty: The work bridges the gap between preference-based RL (which typically handles tabular or linear settings) and kernel-based function approximation (which handles nonlinear settings). It introduces new techniques for handling the lack of smoothness in GP exploration noise within the context of value iteration.
• Computational Efficiency: Unlike previous no-regret algorithms for smooth MDPs that may require intractable optimization, PROSTO offers a polynomial-time implementation.
• Limitations: The authors acknowledge that the regret bound may not be order-optimal. They note that domain partitioning approaches, which currently offer order-optimal bounds in some kernel settings, are incompatible with trajectory-level feedback due to the stochasticity of transitions preventing localized Bellman operator estimation.

The paper concludes that while the derived regret bound is sublinear, achieving an order-optimal bound remains an open question, likely requiring fundamentally different techniques beyond current domain partitioning or uniform covering methods.