Provably More Efficient Q-Learning in the One-Sided-Feedback/Full-Feedback Settings
Motivated by the episodic version of the classical inventory control problem, we propose a new Q-learning-based algorithm, Elimination-Based Half-Q-Learning (HQL), that enjoys improved efficiency over existing algorithms for a wide variety of problems in the one-sided-feedback setting. We also provide a simpler variant of the algorithm, Full-Q-Learning (FQL), for the full-feedback setting. We establish that HQL incurs $ \tilde{\mathcal{O}}(H^3\sqrt{ T})$ regret and FQL incurs $\tilde{\mathcal{O}}(H^2\sqrt{ T})$ regret, where $H$ is the length of each episode and $T$ is the total length of the horizon. The regret bounds are not affected by the possibly huge state and action space. Our numerical experiments demonstrate the superior efficiency of HQL and FQL, and the potential to combine reinforcement learning with richer feedback models.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Deep Learning for CSI Feedback: One-Sided Model and Joint Multi-Module Learning Perspectives
The use of deep learning (DL) for channel state information (CSI) feedback has garnered widespread attention across academia and industry. The mainstream DL architectures, e.g., CsiNet, deploy DL models on the base stati…
An IPW-based Unbiased Ranking Metric in Two-sided Markets
In modern recommendation systems, unbiased learning-to-rank (LTR) is crucial for prioritizing items from biased implicit user feedback, such as click data. Several techniques, such as Inverse Propensity Weighting (IPW), …
Learning-To-RankPositionRecommendation SystemsIndividually Fair Learning with One-Sided Feedback
We consider an online learning problem with one-sided feedback, in which the learner is able to observe the true label only for positively predicted instances. On each round, $k$ instances arrive and receive classificati…
FairnessSeller-Side Experiments under Interference Induced by Feedback Loops in Two-Sided Platforms
Two-sided platforms are central to modern commerce and content sharing and often utilize A/B testing for developing new features. While user-side experiments are common, seller-side experiments become crucial for specifi…
counterfactualPrivacy Preserving Reinforcement Learning with One-Sided Feedback
We study reinforcement learning (RL) in multi-dimensional continuous state and action spaces with one-sided feedback, where the agent receives partial observations of the state and obtains reward information for only a s…
Reinforcement Learning