English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider two-player zero-sum stochastic games and propose a two-timescale$Q$-learning algorithm with function approximation that is payoff-based,convergent, rational, and symmetric between the two players. In two-timescale$Q$-learning, the fast-timescale iterates are updated in spirit to thestochastic gradient descent and the slow-timescale iterates (which we use tocompute the policies) are updated by taking a convex combination between itsprevious iterate and the latest fast-timescale iterate. Introducing the slowtimescale as well as its update equation marks as our main algorithmic novelty.In the special case of linear function approximation, we establish, to the bestof our knowledge, the first last-iterate finite-sample bound for payoff-basedindependent learning dynamics of these types. The result implies a polynomialsample complexity to find a Nash equilibrium in such stochastic games.  To establish the results, we model our proposed algorithm as a two-timescalestochastic approximation and derive the finite-sample bound through aLyapunov-based approach. The key novelty lies in constructing a valid Lyapunovfunction to capture the evolution of the slow-timescale iterates. Specifically,through a change of variable, we show that the update equation of theslow-timescale iterates resembles the classical smoothed best-responsedynamics, where the regularized Nash gap serves as a valid Lyapunov function.This insight enables us to construct a valid Lyapunov function via ageneralized variant of the Moreau envelope of the regularized Nash gap. Theconstruction of our Lyapunov function might be of broad independent interest instudying the behavior of stochastic approximation algorithms.

Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games