Learning Adversarial Low-rank Markov Decision Processes With Unknown Transition And Full-information Feedback

Abstract

In this work, we study the low-rank MDPs with adversarially changed losses in the full-information feedback setting. In particular, the unknown transition probability kernel admits a low-rank matrix decomposition \citep\{REPUCB22\}, and the loss functions may change adversarially but are revealed to the learner at the end of each episode. We propose a policy optimization-based algorithm POLO, and we prove that it attains the \(\widetilde\{O\}(K^\{\frac\{5\}\{6\}\}A^\{\frac\{1\}\{2\}\}d\ln(1+M)/(1-\gamma)^2)\) regret guarantee, where \(d\) is rank of the transition kernel (and hence the dimension of the unknown representations), \(A\) is the cardinality of the action space, \(M\) is the cardinality of the model class, and \(\gamma\) is the discounted factor. Notably, our algorithm is oracle-efficient and has a regret guarantee with no dependence on the size of potentially arbitrarily large state space. Furthermore, we also prove an \(Ω(\frac\{\gamma^2\}\{1-\gamma\} \sqrt\{d A K\})\) reg

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhao2023learning

Related papers

• Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps (2021)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Online Markov Decision Processes With Aggregate Bandit Feedback (2021)0.00
• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00