Adaptive Submodular Policy Optimization

We propose KL-regularized policy optimization for adaptive submodular maximization, which is a framework for decision making under uncertainty with submodular rewards. Policy optimization of adaptive submodular functions justifies a surprisingly simple and efficient policy gradient update, where the optimized action only affects its immediate reward but not the future ones. It also allows us to learn adaptive submodular policies with large action spaces, such as those represented by large language models (LLMs). We prove that our policies monotonically improve as the regularization diminishes and converge to the optimal greedy policy. Our experiments show major gains in statistical efficiency, in both synthetic problems and LLMs.

Authors

• Branislav Kveton Adobe Research
• Anup Rao
• Viet Dac Lai
• Nikos Vlassis Adobe Research
• David Arbour Adobe Research

Keywords

No keywords are indexed for this paper.