POND: Pessimistic-Optimistic oNline Dispatching
This paper considers constrained online dispatching with unknown arrival, reward and constraint distributions. We propose a novel online dispatching algorithm, named POND, standing for Pessimistic-Optimistic oNline Dispatching, which achieves $O(\sqrt{T})$ regret and $O(1)$ constraint violation. Both bounds are sharp. Our experiments on synthetic and real datasets show that POND achieves low regret with minimal constraint violations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimistic and pessimistic approaches for cooperative games
Cooperative game theory studies how to allocate the joint value generated by a set of players. These games are typically analyzed using the characteristic function form with transferable utility, which represents the val…
Balanced Q-learning: Combining the Influence of Optimistic and Pessimistic Targets
The optimistic nature of the Q-learning target leads to an overestimation bias, which is an inherent problem associated with standard $Q-$learning. Such a bias fails to account for the possibility of low returns, particu…
Q-LearningOptimistic Exploration even with a Pessimistic Initialisation
Optimistic initialisation is an effective strategy for efficient exploration in reinforcement learning (RL). In the tabular case, all provably efficient model-free algorithms rely on it. However, model-free deep RL algor…
Efficient ExplorationQ-LearningReinforcement LearningReinforcement Learning (RL)Bayesian Design Principles for Offline-to-Online Reinforcement Learning
Offline reinforcement learning (RL) is crucial for real-world applications where exploration can be costly or unsafe. However, offline learned policies are often suboptimal, and further online fine-tuning is required. In…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Hyperparameter Tuning Through Pessimistic Bilevel Optimization
Automated hyperparameter search in machine learning, especially for deep learning models, is typically formulated as a bilevel optimization problem, with hyperparameter values determined by the upper level and the model …
Bilevel OptimizationHyperparameter Optimization