Zheng Zhijie

Efficient Offline Policy Optimization under All-Policy Linear Q-Realizability

We study offline policy optimization in finite-horizon Markov decision processes with a finite action set and a known bounded feature map. We assume that the action-value function of every randomized memoryless policy is exactly linear, with coefficient norm at most B, and that t...

A Deterministic Algorithm for Minimum Witness Convolution Below the Three-Halves Exponent

Given two length-n Boolean arrays, minimum witness convolution asks, for each output position k, for the least index i with A[i]B[k − i] = 1. We give a deterministic algorithm taking Õ(n1.49644) time, and therefore O(n1.49645) time, on a word RAM with O(log n)-bit words. The cons...

Sharp Half-Density Language Generation with Self-Replay Using Membership Queries

We study language generation from a complete enumeration of an unknown member of a countable family of infinite languages, when the input stream may also replay any earlier output, including erroneous outputs. We prove that a single deterministic oracle algorithm, using only memb...