6 papers
BayesBench: Evaluating LLM Belief Trajectories Under Multi-Turn Evidence Accumulation
Ankur Samanta, Akshayaa Magesh, Tal Lancewicki +7
Large language models (LLMs) are typically deployed in multi-turn conversations, where each turn provides new evidence that should reduce epistemic uncertainty about their environm…
Online Learning in MDPs with Partially Adversarial Transitions and Losses
Ofir Schlisselberg, Tal Lancewicki, Yishay Mansour
We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of steps per episode. This model c…
Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Idan Barnea, Tal Lancewicki, Yishay Mansour
We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We analyzed a variant of Cooperat…
Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
Ofir Schlisselberg, Tal Lancewicki, Peter Auer +1
We study the multi-armed bandit problem with adversarially chosen delays in the Best-of-Both-Worlds (BoBW) framework, which aims to achieve near-optimal performance in both stochas…
Regret Minimization and Convergence to Equilibria in General-sum Markov Games
Liad Erez, Tal Lancewicki, Uri Sherman +2
An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Ne…
Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Tal Lancewicki, Yishay Mansour
We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent…