Fully Dynamic Online Selection through Online Contention Resolution Schemes
We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and stochastic probing problems subject to combinatorial constraints. In the classical ``incremental'' version of the problem, selected elements remain active until the end of the input sequence. On the other hand, in the fully dynamic version of the problem, elements stay active for a limited time interval, and then leave. This models, for example, the online matching of tasks to workers with task/worker-dependent working times, and sequential posted pricing of perishable goods. A successful approach to online selection problems in the adversarial setting is given by the notion of Online Contention Resolution Scheme (OCRS), that uses a priori information to formulate a linear relaxation of the underlying optimization problem, whose optimal fractional solution is rounded online for any adversarial order of the input sequence. Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Enhancing Offline Model-Based RL via Active Model Selection: A Bayesian Optimization Perspective
Offline model-based reinforcement learning (MBRL) serves as a competitive framework that can learn well-performing policies solely from pre-collected data with the help of learned dynamics models. To fully unleash the po…
Bayesian OptimizationmodelModel-based Reinforcement LearningModel Selection+2Joint Sensor Node Selection and State Estimation for Nonlinear Networks and Systems
State estimation and sensor selection problems for nonlinear networks and systems are ubiquitous problems that are important for the control, monitoring, analysis, and prediction of a large number of engineered and physi…
State EstimationTowards Understanding Sensor and Control Nodes Selection in Nonlinear Dynamic Systems: Lyapunov Theory Meets Branch-and-Bound
Sensor and actuator selection problems (SASP) are some of the core problems in dynamic systems design and control. These problems correspond to determining the optimal selection of sensors (measurements) or actuators (co…
validOnline Group Feature Selection
Online feature selection with dynamic features has become an active research area in recent years. However, in some real-world applications such as image analysis and email spam filtering, features may arrive by groups. …
feature selectionDESlib: A Dynamic ensemble selection library in Python
DESlib is an open-source python library providing the implementation of several dynamic selection techniques. The library is divided into three modules: (i) \emph{dcs}, containing the implementation of dynamic classifier…