6 citations · 8 across the 8 of their papers we have counts for
10 papers
On the Computational Tractability of Robust Bandits
Vanessa Kosoy, Vinayak Pathak
Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised lea…
Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity
Vanessa Kosoy
In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called A…
Stringological sequence prediction II: Right-to-left automaticity and related complexity measures
Vanessa Kosoy
In a previous paper, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. One measure we considered was left-to-right (most-sign…
Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences
Vanessa Kosoy
We propose novel algorithms for sequence prediction based on ideas from stringology. These algorithms are time and space efficient and satisfy mistake bounds related to particular…
Ambiguous Online Learning
Vanessa Kosoy
We propose a new variant of online learning that we call "ambiguous online learning". In this setting, the learner is allowed to produce multiple predicted labels. Such an "ambiguo…
Regret Bounds for Robust Online Decision Making
Alexander Appel, Vanessa Kosoy
We propose a framework which generalizes "decision making with structured observations" by allowing robust (i.e. multivalued) models. In this framework, each model associates each…
Imprecise Multi-Armed Bandits
Vanessa Kosoy
We introduce a novel multi-armed bandit framework, where each arm is associated with a fixed unknown credal set over the space of outcomes (which can be richer than just the reward…
Time complexity for deterministic string machines
Nur Cataltepe, Vanessa Kosoy
Algorithms which learn environments represented by automata in the past have had complexity scaling with the number of states in the automaton, which can be exponentially large eve…
Delegative Reinforcement Learning: learning to avoid traps with a little help
Vanessa Kosoy
Most known regret bounds for reinforcement learning are either episodic or assume an environment without traps. We derive a regret bound without making either assumption, by allowi…
Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
Vanessa Kosoy, Alexander Appel
We introduce a new concept of approximation applicable to decision problems and functions, inspired by Bayesian probability. From the perspective of a Bayesian reasoner with limite…