Timezone: »
Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes. The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function. Our result is applicable in Reinforcement Learning (RL). In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for off-policy TD-learning [18]. Importantly, our construction results in only a logarithmic dependence of the convergence bound on the size of the state-space.
Author Information
Zaiwei Chen (Georgia Institute of Technology)
Siva Theja Maguluri (Georgia Institute of Technology)
Sanjay Shakkottai (University of Texas at Austin)
Karthikeyan Shanmugam (IBM Research, NY)
More from the Same Authors
-
2022 : Learning Certifiably Robust Controllers Using Fragile Perception »
Dawei Sun · Negin Musavi · Geir Dullerud · Sanjay Shakkottai · Sayan Mitra -
2022 : Learning Certifiably Robust Controllers Using Fragile Perception »
Dawei Sun · Negin Musavi · Geir Dullerud · Sanjay Shakkottai · Sayan Mitra -
2023 Poster: Identifiability Guarantees for Causal Disentanglement from Soft Interventions »
Jiaqi Zhang · Kristjan Greenewald · Chandler Squires · Akash Srivastava · Karthikeyan Shanmugam · Caroline Uhler -
2023 Poster: Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledge »
Abhin Shah · Karthikeyan Shanmugam · Murat Kocaoglu -
2023 Poster: Solving Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models »
Litu Rout · Negin Raoof · Giannis Daras · Constantine Caramanis · Alex Dimakis · Sanjay Shakkottai -
2023 Poster: Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints »
Soumyabrata Pal · Arun Suggala · Karthikeyan Shanmugam · Prateek Jain -
2022 Poster: Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret »
Orestis Papadigenopoulos · Constantine Caramanis · Sanjay Shakkottai -
2022 Poster: Minimax Regret for Cascading Bandits »
Daniel Vial · Sujay Sanghavi · Sanjay Shakkottai · R. Srikant -
2022 Poster: Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations »
Amit Dhurandhar · Karthikeyan Natesan Ramamurthy · Karthikeyan Shanmugam -
2022 Poster: FedAvg with Fine Tuning: Local Updates Lead to Representation Learning »
Liam Collins · Hamed Hassani · Aryan Mokhtari · Sanjay Shakkottai -
2021 Poster: CoFrNets: Interpretable Neural Architecture Inspired by Continued Fractions »
Isha Puri · Amit Dhurandhar · Tejaswini Pedapati · Karthikeyan Shanmugam · Dennis Wei · Kush Varshney -
2021 Poster: Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators »
Zaiwei Chen · Siva Theja Maguluri · Sanjay Shakkottai · Karthikeyan Shanmugam -
2021 Poster: Finite Sample Analysis of Average-Reward TD Learning and $Q$-Learning »
Sheng Zhang · Zhe Zhang · Siva Theja Maguluri -
2021 Poster: Scalable Intervention Target Estimation in Linear Models »
Burak Varici · Karthikeyan Shanmugam · Prasanna Sattigeri · Ali Tajer -
2020 Poster: Active Structure Learning of Causal DAGs via Directed Clique Trees »
Chandler Squires · Sara Magliacane · Kristjan Greenewald · Dmitriy Katz · Murat Kocaoglu · Karthikeyan Shanmugam -
2020 Poster: Task-Robust Model-Agnostic Meta-Learning »
Liam Collins · Aryan Mokhtari · Sanjay Shakkottai -
2020 Poster: Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning »
Amin Jaber · Murat Kocaoglu · Karthikeyan Shanmugam · Elias Bareinboim -
2020 Poster: Mix and Match: An Optimistic Tree-Search Approach for Learning Models from Mixture Distributions »
Matthew Faw · Rajat Sen · Karthikeyan Shanmugam · Constantine Caramanis · Sanjay Shakkottai -
2020 Poster: Applications of Common Entropy for Causal Inference »
Murat Kocaoglu · Sanjay Shakkottai · Alex Dimakis · Constantine Caramanis · Sriram Vishwanath -
2020 Poster: Learning Global Transparent Models consistent with Local Contrastive Explanations »
Tejaswini Pedapati · Avinash Balakrishnan · Karthikeyan Shanmugam · Amit Dhurandhar -
2019 : Poster and Coffee Break 1 »
Aaron Sidford · Aditya Mahajan · Alejandro Ribeiro · Alex Lewandowski · Ali H Sayed · Ambuj Tewari · Angelika Steger · Anima Anandkumar · Asier Mujika · Hilbert J Kappen · Bolei Zhou · Byron Boots · Chelsea Finn · Chen-Yu Wei · Chi Jin · Ching-An Cheng · Christina Yu · Clement Gehring · Craig Boutilier · Dahua Lin · Daniel McNamee · Daniel Russo · David Brandfonbrener · Denny Zhou · Devesh Jha · Diego Romeres · Doina Precup · Dominik Thalmeier · Eduard Gorbunov · Elad Hazan · Elena Smirnova · Elvis Dohmatob · Emma Brunskill · Enrique Munoz de Cote · Ethan Waldie · Florian Meier · Florian Schaefer · Ge Liu · Gergely Neu · Haim Kaplan · Hao Sun · Hengshuai Yao · Jalaj Bhandari · James A Preiss · Jayakumar Subramanian · Jiajin Li · Jieping Ye · Jimmy Smith · Joan Bas Serrano · Joan Bruna · John Langford · Jonathan Lee · Jose A. Arjona-Medina · Kaiqing Zhang · Karan Singh · Yuping Luo · Zafarali Ahmed · Zaiwei Chen · Zhaoran Wang · Zhizhong Li · Zhuoran Yang · Ziping Xu · Ziyang Tang · Yi Mao · David Brandfonbrener · Shirli Di-Castro · Riashat Islam · Zuyue Fu · Abhishek Naik · Saurabh Kumar · Benjamin Petit · Angeliki Kamoutsi · Simone Totaro · Arvind Raghunathan · Rui Wu · Donghwan Lee · Dongsheng Ding · Alec Koppel · Hao Sun · Christian Tjandraatmadja · Mahdi Karami · Jincheng Mei · Chenjun Xiao · Junfeng Wen · Zichen Zhang · Ross Goroshin · Mohammad Pezeshki · Jiaqi Zhai · Philip Amortila · Shuo Huang · Mariya Vasileva · El houcine Bergou · Adel Ahmadyan · Haoran Sun · Sheng Zhang · Lukas Gruber · Yuanhao Wang · Tetiana Parshakova -
2019 Poster: Differentially Private Distributed Data Summarization under Covariate Shift »
Kanthi Sarpatwar · Karthikeyan Shanmugam · Venkata Sitaramagiridharganesh Ganapavarapu · Ashish Jagmohan · Roman Vaculin -
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix-Adsera · Guy Bresler -
2019 Poster: Blocking Bandits »
Soumya Basu · Rajat Sen · Sujay Sanghavi · Sanjay Shakkottai -
2019 Poster: Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions »
Murat Kocaoglu · Amin Jaber · Karthikeyan Shanmugam · Elias Bareinboim -
2018 Poster: Improving Simple Models with Confidence Profiles »
Amit Dhurandhar · Karthikeyan Shanmugam · Ronny Luss · Peder A Olsen -
2018 Poster: Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives »
Amit Dhurandhar · Pin-Yu Chen · Ronny Luss · Chun-Chen Tu · Paishun Ting · Karthikeyan Shanmugam · Payel Das -
2017 Poster: Experimental Design for Learning Causal Graphs with Latent Variables »
Murat Kocaoglu · Karthikeyan Shanmugam · Elias Bareinboim -
2017 Poster: Model-Powered Conditional Independence Test »
Rajat Sen · Ananda Theertha Suresh · Karthikeyan Shanmugam · Alex Dimakis · Sanjay Shakkottai -
2016 Poster: Regret of Queueing Bandits »
Subhashini Krishnasamy · Rajat Sen · Ramesh Johari · Sanjay Shakkottai -
2015 Poster: Learning Causal Graphs with Small Interventions »
Karthikeyan Shanmugam · Murat Kocaoglu · Alex Dimakis · Sriram Vishwanath -
2014 Poster: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alex Dimakis · Adam Klivans -
2014 Poster: On the Information Theoretic Limits of Learning Ising Models »
Rashish Tandon · Karthikeyan Shanmugam · Pradeep Ravikumar · Alex Dimakis -
2014 Oral: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alex Dimakis · Adam Klivans