Gaussian Process Based Optimistic Knapsack Sampling with Applications to Stochastic Resource Allocation

Sondre Glimsdal, Ole-Christoffer GranmoMAICS 2013 · OpenReview

Abstract

This paper introduces Gaussian Process based Optimistic Knapsack Sampling (GPOKS), a novel reinforcement learning framework designed to solve the Stochastic Non-linear Equality Fractional Knapsack (NEFK) problem. By integrating Gaussian Processes for uncertainty modeling with an optimistic variant of Thompson Sampling, GPOKS effectively balances exploration and exploitation in environments with unknown, non-linear reward functions. Experimental results in simulated web polling scenarios demonstrate that GPOKS significantly outperforms traditional learning automata-based methods, achieving faster convergence and higher resource utilization efficiency even in the presence of significant noise.

Introduction

Efficient resource allocation is a critical challenge in systems where the value of resources is both non-linear and initially unknown. A prime example is web polling for search engines, where limited bandwidth must be distributed across thousands of pages to maximize the detection of updates. This problem is characterized by diminishing returns—more frequent polling of a single page yields fewer new discoveries per poll—and stochasticity, as page change rates are unknown and potentially dynamic.

The authors formalize this as the Stochastic Non-linear Equality Fractional Knapsack (NEFK) problem. While traditional optimization techniques like Lagrange multipliers can solve deterministic versions of this problem, they fail when the underlying value functions are unknown. Previous adaptive approaches, such as the Learning Automata Knapsack Game (LAKG), often suffer from slow convergence. GPOKS addresses these limitations by adopting a model-based Bayesian approach.

The GPOKS Framework

The GPOKS algorithm combines three sophisticated components to navigate the exploration-exploitation trade-off:

  1. Gaussian Processes (GPs): GPOKS maintains a GP for each resource, providing a full probability distribution over possible value functions. This allows the agent to quantify uncertainty across the entire action space.
  2. Optimistic Thompson Sampling (OTS): To select actions, the algorithm samples from the GP posterior. Crucially, it employs an "optimistic" filter, rejecting samples that fall below the current mean. This ensures the agent prioritizes exploration in uncertain regions rather than settling for sub-optimal but "safe" actions.
  3. Deterministic Knapsack Solver (DET-KS): Once a candidate value function is sampled, the problem is treated as deterministic. A Lagrange multiplier-based solver identifies the mathematically optimal resource distribution for that specific sample.
The GPOKS architecture integrating Gaussian Processes with a deterministic knapsack solver.

Decision Making under Uncertainty

The core innovation of GPOKS lies in how it uses the GP model to drive scheduling decisions. By sampling a function from the GP, the algorithm acts as if that sample represents the true environment. Over time, as more feedback is received from the stochastic environment, the GP posterior narrows, and the sampled functions converge toward the true value function.

Visualization of the GP posterior and the resulting estimated resource allocation compared to the true optimal.

As shown in the figure above, the "estimated x1" derived from a sampled function (green line) approaches the "optimal x1" as the GP mean (red line) and uncertainty band (yellow) are refined through interaction. The optimistic sampling mechanism prevents the algorithm from becoming overly conservative in the face of noisy feedback.

Experimental Evaluation

The performance of GPOKS was evaluated against the LAKG method and uniform allocation strategies across various simulated web environments. Key findings include:

  • Superior Convergence: GPOKS reached near-optimal performance significantly faster than model-free alternatives like LAKG.
  • Increased Efficiency: In scenarios with diverse update rates (e.g., $q_1=0.9, q_2=0.1$), GPOKS detected approximately 903 updates over 1,000 steps, nearing the theoretical maximum of 910 and surpassing LAKG's 875.
  • Robustness: The algorithm proved resilient to environmental noise. Under high white noise conditions ($w_\sigma = 0.4$), GPOKS maintained high performance (804.1 updates), whereas a non-optimistic "greedy" version (GPOKS-Mean) saw a significant performance drop to 769.1.

Conclusion

GPOKS represents a significant advancement in solving stochastic resource allocation problems with non-linear rewards. By leveraging the predictive power of Gaussian Processes and the exploratory drive of Optimistic Thompson Sampling, it provides a robust and efficient framework for real-world applications like web crawling. Future research will focus on reducing the computational complexity of GP calculations to improve scalability and extending the framework to handle interacting agents in networked environments.

Summary updated

BibTeX
@inproceedings{glimsdal2013gaussian,
  author = {Sondre Glimsdal and Ole-Christoffer Granmo},
  title = {{Gaussian Process Based Optimistic Knapsack Sampling with Applications to Stochastic Resource Allocation}},
  booktitle = {MAICS},
  year = {2013},
  url = {https://openreview.net/forum?id=OlYWRc0ZV-},
}
Figure