9 papers
Optimal No-Regret Learning for Repeated Prophet Inequality
Kun Wang
We study repeated prophet inequalities under prefix feedback. In each of rounds, a learner encounters fresh values drawn independently from boxes with unknown -suppo…
A Complete Characterization of Learnability for Adversarial Noisy Bandits
Steve Hanneke, Kun Wang
We study adversarial noisy bandits given a known function class . In each round, the adversary selects a function , the learner chooses an arm, and…
Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem
Yuefeng Lin, Kun Wang, Qinyuan Zheng +6
MaxCut is a canonical NP-hard combinatorial optimization problem in graph theory with broad applications ranging from physics to bioinformatics. Although variational quantum algori…
A note on Cybenko's Universal Approximation Theorem
Kun Wang
In this short note, we point out a mistake in G.Cybenko's proof of his version of the universal approximation theorem which has been widely cited. This mistake might not be easily…
Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
Junyan Liu, Ziyun Chen, Kun Wang +2
We study the Pandora's Box problem in an online learning setting with semi-bandit feedback. In each round, the learner sequentially pays to open up to boxes with unknown reward…
Imitation Learning of Correlated Policies in Stackelberg Games
Kuang-Da Wang, Ping-Chun Hsieh, Wen-Chih Peng
Stackelberg games, widely applied in domains like economics and security, involve asymmetric interactions where a leader's strategy drives follower responses. Accurately modeling t…
A Complete Characterization of Learnability for Stochastic Noisy Bandits
Steve Hanneke, Kun Wang
We study the stochastic noisy bandit problem with an unknown reward function in a known function class . Formally, a model maps arms to a probability dis…
Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
Simina Brânzei, MohammadTaghi Hajiaghayi, Reed Phillips +2
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is ident…
Fidelity Estimation of Entangled Measurements with Local States
Zanqiu Shen, Kun Wang
We propose an efficient protocol to estimate the fidelity of an -qubit entangled measurement device, requiring only qubit state preparations and classical data post-processing.…