More Like this

1. TLdR: Policy Summarization for Factored SSP Problems Using Temporal Abstractions

   Sarath Sreedharan, Siddharth Srivastava (May 2020, Proceedings of the International Conference on Automated Planning and Scheduling)

   As more and more people are expected to work with complex AI-systems, it becomes more important than ever that such systems provide intuitive explanations for their decisions. A prerequisite for holding such explanatory dialogue is the ability of the systems to present their proposed decisions to the user in an easy-to-understand form. Unfortunately, such dialogues could become hard to facilitate in real-world problems where the system may be planning for multiple eventualities in stochastic environments. This means for the system to be effective, it needs to be able to present the policy at a high-level of abstraction and delve into details as required. Towards this end, we investigate the utility of temporal abstractions derived through analytically computed landmarks and their relative ordering to build a summarization of policies for Stochastic Shortest Path Problems. We formalize the concept of policy landmarks and show how it can be used to provide a high level overview of a given policy. Additionally, we establish the connections between the type of hierarchy we generate and previous works in temporal abstractions, specifically MaxQ hierarchies. Our approach is evaluated through user studies as well as empirical metrics that establish that people tend to choose landmarks facts as subgoals to summarize policies and demonstrates the performance of our approach on standard benchmarks. 

   more » « less
2. Balanced Policy Evaluation and Learning

   Kallus, Nathan (January 2018, Advances in neural information processing systems)

   We present a new approach to the problems of evaluating and learning personalized decision policies from observational data of past contexts, decisions, and outcomes. Only the outcome of the enacted decision is available and the historical policy is unknown. These problems arise in personalized medicine using electronic health records and in internet advertising. Existing approaches use inverse propensity weighting (or, doubly robust versions) to make historical outcome (or, residual) data look like it were generated by a new policy being evaluated or learned. But this relies on a plug-in approach that rejects data points with a decision that disagrees with the new policy, leading to high variance estimates and ineffective learning. We propose a new, balance-based approach that too makes the data look like the new policy but does so directly by finding weights that optimize for balance between the weighted data and the target policy in the given, finite sample, which is equivalent to minimizing worst-case or posterior conditional mean square error. Our policy learner proceeds as a two-level optimization problem over policies and weights. We demonstrate that this approach markedly outperforms existing ones both in evaluation and learning, which is unsurprising given the wider support of balance-based weights. We establish extensive theoretical consistency guarantees and regret bounds that support this empirical success. 

   more » « less
3. Index-aware reinforcement learning for adaptive video streaming at the wireless edge

   https://doi.org/10.1145/3492866.3549726  

   Xiong, Guojun; Qin, Xudong; Li, Bin; Singh, Rahul; Li, Jian (October 2022, MobiHoc '22: Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing)

   We study adaptive video streaming for multiple users in wireless access edge networks with unreliable channels. The key challenge is to jointly optimize the video bitrate adaptation and resource allocation such that the users' cumulative quality of experience is maximized. This problem is a finite-horizon restless multi-armed multi-action bandit problem and is provably hard to solve. To overcome this challenge, we propose a computationally appealing index policy entitled Quality Index Policy, which is well-defined without the Whittle indexability condition and is provably asymptotically optimal without the global attractor condition. These two conditions are widely needed in the design of most existing index policies, which are difficult to establish in general. Since the wireless access edge network environment is highly dynamic with system parameters unknown and time-varying, we further develop an index-aware reinforcement learning (RL) algorithm dubbed QA-UCB. We show that QA-UCB achieves a sub-linear regret with a low-complexity since it fully exploits the structure of the Quality Index Policy for making decisions. Extensive simulations using real-world traces demonstrate significant gains of proposed policies over conventional approaches. We note that the proposed framework for designing index policy and index-aware RL algorithm is of independent interest and could be useful for other large-scale multi-user problems. 

   more » « less
4. Conditional abstraction trees for sample-efficient reinforcement learning

   Dadvar, Mehdi; Nayyar, Rashmeet K; Srivastava, Siddharth (September 2023, Proceedings of Machine Learning Research)

   In many real-world problems, the learning agent needs to learn a problem’s abstractions and solution simultaneously. However, most such abstractions need to be designed and refined by hand for different problems and domains of application. This paper presents a novel top-down approach for constructing state abstractions while carrying out reinforcement learning (RL). Starting with state variables and a simulator, it presents a novel domain-independent approach for dynamically computing an abstraction based on the dispersion of temporal difference errors in abstract states as the agent continues acting and learning. Extensive empirical evaluation on multiple domains and problems shows that this approach automatically learns semantically rich abstractions that are finely-tuned to the problem, yield strong sample efficiency, and result in the RL agent significantly outperforming existing approaches. 

   more » « less
5. Visually Introducing Freshmen to Low-Level Java Abstractions for Creating, Synchronizing and Coordinating Threads

   https://doi.org/10.1109/HiPCW.2019.00022  

   Dewan, Prasun (December 2019, 2019 26th International Conference on High Performance Computing, Data and Analytics Workshop (HiPCW))

   We have developed and experimented with an approach to teach low-level Java concurrency abstractions in our first required course for CS majors, which assumes knowledge of procedural programming. The driving problems are visualized simulations of multiple physical objects in motion that may (a) be confined to a shared space and (b) coordinate with each other. Such simulations do not require any domain-specific knowledge such as sorting and image processing for driving problems and exercises, and their implementation demonstrates the benefits of object-based programming. They allow focus on both the performance and programmability benefits of concurrency, provide analogies for an abstraction-independent explanation of concurrency concepts, and can be used to incrementally motivate all low-level concurrency abstractions and visualize the effect of using and not using these abstractions. Layered simulation-based worked examples illustrating the abstractions were presented and easily understood in multiple offerings of a course that implemented this approach. Students implemented non-trivial assignments based on these abstractions, even when they were optional, did not face major obstacles because of visual error feedback, and were excited by concurrency as they felt it empowered them to implement arbitrary applications early. 

   more » « less