Koundinya Vajjha

Koundinya Vajjha

Auto-generated profile, based on publicly available information

Koundinya Vajjha

University of Pittsburgh, USA

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
17 January 2021
Verified
Conference Paper
Open access
JTJoseph Tassarotti
Joseph Tassarotti
KVKoundinya Vajjha
Koundinya Vajjha
ABAnindya Banerjee
Anindya Banerjee
JTJean-Baptiste Tristan
Jean-Baptiste Tristan
We present a formal proof in Lean of probably approximately correct (PAC) learnability of the concept class of decision stumps. This classic result in machine learning theory derives a bound on error probabilities for a simple type of classifier. Though such a proof appears simple on paper, analytic and measure-theoretic subtleties arise when carrying it out fully formally. Our proof is structured so as to separate reasoning about deterministic properties of a learning function from proofs of measurability and analysis of probabilities.

17 January 2021
Verified
Conference Paper
Open access
KVKoundinya Vajjha
Koundinya Vajjha
ASAvraham Shinnar
Avraham Shinnar
BTBarry Trager
Barry Trager
VPVasily Pestun
Vasily Pestun
NFNathan Fulton
Nathan Fulton
Reinforcement learning algorithms solve sequential decision-making problems in probabilistic environments by optimizing for long-term reward. The desire to use reinforcement learning in safety-critical settings inspires a recent line of work on formally constrained reinforcement learning; however, these methods place the implementation of the learning algorithm in their Trusted Computing Base. The crucial correctness property of these implementations is a guarantee that the learning algorithm converges to an optimal policy. This paper begins the work of closing this gap by developing a Coq formalization of two canonical reinforcement learning algorithms: value and policy iteration for finite state Markov decision processes. The central results are a formalization of the Bellman optimality principle and its proof, which uses a contraction property of Bellman optimality operator to establish that a sequence converges in the infinite horizon limit. The CertRL development exemplifies how the Giry monad and mechanized metric coinduction streamline optimality proofs for reinforcement learning algorithms. The CertRL library provides a general framework for proving properties about Markov decision processes and reinforcement learning algorithms, paving the way for further work on formalization of reinforcement learning algorithms.

8 August 2022 in arXiv
Verified
Preprint
Open access
PDF file
KVKoundinya Vajjha
Koundinya Vajjha
BTBarry Trager
Barry Trager
ASAvraham Shinnar
Avraham Shinnar
VPVasily Pestun
Vasily Pestun
Stochastic approximation algorithms are iterative procedures which are used to approximate a target value in an environment where the target is unknown and direct observations are corrupted by noise. These algorithms are useful, for instance, for root-finding and function minimization when the target function or model is not directly known. Originally introduced in a 1951 paper by Robbins and Monro, the field of Stochastic approximation has grown enormously and has come to influence application domains from adaptive signal processing to artificial intelligence. As an example, the Stochastic Gradient Descent algorithm which is ubiquitous in various subdomains of Machine Learning is based on stochastic approximation theory. In this paper, we give a formal proof (in the Coq proof assistant) of a general convergence theorem due to Aryeh Dvoretzky, which implies the convergence of important classical methods such as the Robbins-Monro and the Kiefer-Wolfowitz algorithms. In the process, we build a comprehensive Coq library of measure-theoretic probability theory and stochastic processes.