Yagiz Savas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Yagiz Savas has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Ufuk Topcu
University of Texas at Austin
10 shared publications - Michael Hibbard
Department of Aerospace Engineering and Engineering Mechanics The University of Texas at Austin
5 shared publications - Abolfazl Hashemi
School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA
2 shared publications - Brian M. Sadler
Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, TX 78712, USA
2 shared publications - Mustafa O. Karabag
The University of Texas at Austin
2 shared publications - Takashi Tanaka
School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN, USA
2 shared publications
Latest Publications
- 3 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 69 (9) , 6466-6473
On Minimizing Total Discounted Cost in MDPs Subject to Reachability Constraints
We study the synthesis of a policy in a Markov decision process (MDP) following which an agent reaches a target state in the MDP while minimizing its total discounted cost. The problem combines a reachability criterion with a discounted cost criterion and naturally expresses the completion of a task with probabilistic guarantees and optimal transient performance. We first establish that an optimal policy for the considered formulation may not exist but that there always exists a near-optimal stationary policy. We additionally provide a necessary and sufficient condition for the existence of an optimal policy. We then restrict our attention to stationary deterministic policies and show that the decision problem associated with the synthesis of an optimal stationary deterministic policy is NP-complete. Finally, we provide an exact algorithm based on mixed-integer linear programming and propose an efficient approximation algorithm based on linear programming for the synthesis of an optimal stationary deterministic policy.
- 3 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 69 (9) , 6466-6473
On Minimizing Total Discounted Cost in MDPs Subject to Reachability Constraints
We study the synthesis of a policy in a Markov decision process (MDP) following which an agent reaches a target state in the MDP while minimizing its total discounted cost. The problem combines a reachability criterion with a discounted cost criterion and naturally expresses the completion of a task with probabilistic guarantees and optimal transient performance. We first establish that an optimal policy for the considered formulation may not exist but that there always exists a near-optimal stationary policy. We additionally provide a necessary and sufficient condition for the existence of an optimal policy. We then restrict our attention to stationary deterministic policies and show that the decision problem associated with the synthesis of an optimal stationary deterministic policy is NP-complete. Finally, we provide an exact algorithm based on mixed-integer linear programming and propose an efficient approximation algorithm based on linear programming for the synthesis of an optimal stationary deterministic policy.
- 6 November 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 69 (3) , 1418-1431
No-Regret Learning in Dynamic Stackelberg Games
In a Stackelberg game , a leader commits to a randomized strategy, and a follower chooses their best strategy in response. We consider an extension of a standard Stackelberg game, called a discrete-time dynamic Stackelberg game , that has an underlying state space that affects the leader's rewards and available strategies and evolves in a Markovian manner depending on both the leader and follower's selected strategies. Although standard Stackelberg games have been utilized to improve scheduling in security domains, their deployment is often limited by requiring complete information of the follower's utility function. In contrast, we consider scenarios where the follower's utility function is unknown to the leader; however, it can be linearly parameterized. Our objective then is to provide an algorithm that prescribes a randomized strategy to the leader at each step of the game based on observations of how the follower responded in previous steps. We design an online learning algorithm that, with high probability, is no-regret , i.e., achieves a regret bound (when compared to the best policy in hindsight) which is sublinear in the number of timesteps; the degree of sublinearity depends on the number of features representing the follower's utility function. The regret of the proposed learning algorithm is independent of the size of the state space and polynomial in the rest of the parameters of the game. We show that the proposed learning algorithm outperforms existing model-free reinforcement learning approaches.
- 6 November 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 69 (3) , 1418-1431
No-Regret Learning in Dynamic Stackelberg Games
In a Stackelberg game , a leader commits to a randomized strategy, and a follower chooses their best strategy in response. We consider an extension of a standard Stackelberg game, called a discrete-time dynamic Stackelberg game , that has an underlying state space that affects the leader's rewards and available strategies and evolves in a Markovian manner depending on both the leader and follower's selected strategies. Although standard Stackelberg games have been utilized to improve scheduling in security domains, their deployment is often limited by requiring complete information of the follower's utility function. In contrast, we consider scenarios where the follower's utility function is unknown to the leader; however, it can be linearly parameterized. Our objective then is to provide an algorithm that prescribes a randomized strategy to the leader at each step of the game based on observations of how the follower responded in previous steps. We design an online learning algorithm that, with high probability, is no-regret , i.e., achieves a regret bound (when compared to the best policy in hindsight) which is sublinear in the number of timesteps; the degree of sublinearity depends on the number of features representing the follower's utility function. The regret of the proposed learning algorithm is independent of the size of the state space and polynomial in the rest of the parameters of the game. We show that the proposed learning algorithm outperforms existing model-free reinforcement learning approaches.
- Open Access
Deceptive Planning for Resource Allocation
We consider a team of autonomous agents that navigate in an adversarial environment and aim to achieve a task by allocating their resources over a set of target locations. An adversary in the environment observes the autonomous team's behavior to infer their objective and responds against the team. In this setting, we propose strategies for controlling the density of the autonomous team so that they can deceive the adversary regarding their objective while achieving the desired final resource allocation. We first develop a prediction algorithm based on the principle of maximum entropy to express the team's behavior expected by the adversary. Then, by measuring the deceptiveness via Kullback-Leibler divergence, we devise convex optimization-based planning algorithms that deceive the adversary by either exaggerating the behavior towards a decoy allocation strategy or creating ambiguity regarding the final allocation strategy. A user study with $320$ participants demonstrates that the proposed algorithms are effective for deception and reveal the inherent biases of participants towards proximate goals.Open AccessDeceptive Planning for Resource Allocation
We consider a team of autonomous agents that navigate in an adversarial environment and aim to achieve a task by allocating their resources over a set of target locations. An adversary in the environment observes the autonomous team's behavior to infer their objective and responds against the team. In this setting, we propose strategies for controlling the density of the autonomous team so that they can deceive the adversary regarding their objective while achieving the desired final resource allocation. We first develop a prediction algorithm based on the principle of maximum entropy to express the team's behavior expected by the adversary. Then, by measuring the deceptiveness via Kullback-Leibler divergence, we devise convex optimization-based planning algorithms that deceive the adversary by either exaggerating the behavior towards a decoy allocation strategy or creating ambiguity regarding the final allocation strategy. A user study with $320$ participants demonstrates that the proposed algorithms are effective for deception and reveal the inherent biases of participants towards proximate goals. - 16 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 67 (12) , 6948-6955
Entropy Maximization for Partially Observable Markov Decision Processes
We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of an agent’s trajectories to an outside observer while guaranteeing the completion of a task expressed by a reward function. Focusing on finite-state controllers (FSCs) with deterministic memory transitions, we show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of the parametric Markov chain (pMC) induced by such FSCs. This relationship allows us to recast the entropy maximization problem as a so-called parameter synthesis problem for the induced pMC. We then present an algorithm to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In a numerical example, we highlight the benefit of using an entropy-maximizing FSC compared to an FSC that simply finds a feasible policy for accomplishing a task.
- 16 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 67 (12) , 6948-6955
Entropy Maximization for Partially Observable Markov Decision Processes
We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of an agent’s trajectories to an outside observer while guaranteeing the completion of a task expressed by a reward function. Focusing on finite-state controllers (FSCs) with deterministic memory transitions, we show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of the parametric Markov chain (pMC) induced by such FSCs. This relationship allows us to recast the entropy maximization problem as a so-called parameter synthesis problem for the induced pMC. We then present an algorithm to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In a numerical example, we highlight the benefit of using an entropy-maximizing FSC compared to an FSC that simply finds a feasible policy for accomplishing a task.
- 2 November 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 67 (11) , 5809-5824
On the Complexity of Sequential Incentive Design
In many scenarios, a principal dynamically interacts with an agent and offers a sequence of incentives to align the agent's behavior with a desired objective. This paper focuses on the problem of synthesizing an incentive sequence that, once offered, induces the desired agent behavior even when the agent's intrinsic motivation is unknown to the principal. We model the agent's behavior as a Markov decision process, express its intrinsic motivation as a reward function, which belongs to a finite set of possible reward functions, and consider the incentives as additional rewards offered to the agent. We first show that the behavior modification problem (BMP), i.e., the problem of synthesizing an incentive sequence that induces a desired agent behavior at minimum total cost to the principal, is PSPACE-hard. Moreover, we obtain two NP-complete variants of the BMP by imposing certain restrictions on the incentive sequences available to the principal. We also provide a sufficient condition on the set of possible reward functions under which the BMP can be solved via linear programming. Finally, we propose two algorithms to solve the NP-complete variants of the BMP.
- 2 November 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 67 (11) , 5809-5824
On the Complexity of Sequential Incentive Design
In many scenarios, a principal dynamically interacts with an agent and offers a sequence of incentives to align the agent's behavior with a desired objective. This paper focuses on the problem of synthesizing an incentive sequence that, once offered, induces the desired agent behavior even when the agent's intrinsic motivation is unknown to the principal. We model the agent's behavior as a Markov decision process, express its intrinsic motivation as a reward function, which belongs to a finite set of possible reward functions, and consider the incentives as additional rewards offered to the agent. We first show that the behavior modification problem (BMP), i.e., the problem of synthesizing an incentive sequence that induces a desired agent behavior at minimum total cost to the principal, is PSPACE-hard. Moreover, we obtain two NP-complete variants of the BMP by imposing certain restrictions on the incentive sequences available to the principal. We also provide a sufficient condition on the set of possible reward functions under which the BMP can be solved via linear programming. Finally, we propose two algorithms to solve the NP-complete variants of the BMP.
- Open Access
- 6 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4685-4689
Physical-Layer Security via Distributed Beamforming in the Presence of Adversaries with Unknown Locations
We study the problem of securely communicating a sequence of information bits with a client in the presence of multiple adversaries at unknown locations in the environment. We assume that the client and the adversaries are located in the far-field region, and all possible directions for each adversary can be expressed as a continuous interval of directions. In such a setting, we develop a periodic transmission strategy, i.e., a sequence of joint beamforming gain and artificial noise pairs, that prevents the adversaries from decreasing their uncertainty on the information sequence by eavesdropping on the transmission. We formulate a series of nonconvex semi-infinite optimization problems to synthesize the transmission strategy. We show that the semi-definite program (SDP) relaxations of these nonconvex problems are exact under an efficiently verifiable sufficient condition. We approximate the SDP relaxations, which are subject to infinitely many constraints, by randomly sampling a finite subset of the constraints and establish the probability with which optimal solutions to the obtained finite SDPs and the semi-infinite SDPs coincide. We demonstrate with numerical simulations that the proposed periodic strategy can ensure the security of communication in scenarios in which all stationary strategies fail to guarantee security.
- 6 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4685-4689
Open AccessPhysical-Layer Security via Distributed Beamforming in the Presence of Adversaries with Unknown Locations
We study the problem of securely communicating a sequence of information bits with a client in the presence of multiple adversaries at unknown locations in the environment. We assume that the client and the adversaries are located in the far-field region, and all possible directions for each adversary can be expressed as a continuous interval of directions. In such a setting, we develop a periodic transmission strategy, i.e., a sequence of joint beamforming gain and artificial noise pairs, that prevents the adversaries from decreasing their uncertainty on the information sequence by eavesdropping on the transmission. We formulate a series of nonconvex semi-infinite optimization problems to synthesize the transmission strategy. We show that the semi-definite program (SDP) relaxations of these nonconvex problems are exact under an efficiently verifiable sufficient condition. We approximate the SDP relaxations, which are subject to infinitely many constraints, by randomly sampling a finite subset of the constraints and establish the probability with which optimal solutions to the obtained finite SDPs and the semi-infinite SDPs coincide. We demonstrate with numerical simulations that the proposed periodic strategy can ensure the security of communication in scenarios in which all stationary strategies fail to guarantee security.
- 1 January 2020
- Published by Elsevier in IFAC-PapersOnLine
- Vol. 53 (2) , 15388-15395
Minimizing the Information Leakage Regarding High-Level Task Specifications
- 1 January 2020
- Published by Elsevier in IFAC-PapersOnLine
- Vol. 53 (2) , 15388-15395
Minimizing the Information Leakage Regarding High-Level Task Specifications
- Open Access
Minimizing the Information Leakage Regarding High-Level Task Specifications
We consider a scenario in which an autonomous agent carries out a mission in a stochastic environment while passively observed by an adversary. For the agent, minimizing the information leaked to the adversary regarding its high-level specification is critical in creating an informational advantage. We express the specification of the agent as a parametric linear temporal logic formula, measure the information leakage by the adversary's confidence in the agent's mission specification, and propose algorithms to synthesize a policy for the agent which minimizes the information leakage to the adversary. In the scenario considered, the adversary aims to infer the specification of the agent from a set of candidate specifications, each of which has an associated likelihood probability. The agent's objective is to synthesize a policy that maximizes the entropy of the adversary's likelihood distribution while satisfying its specification. We propose two approaches to solve the resulting synthesis problem. The first approach computes the exact satisfaction probabilities for each candidate specification, whereas the second approach utilizes the Fr\'echet inequalities to approximate them. For each approach, we formulate a mixed-integer program with a quasiconcave objective function. We solve the problem using a bisection algorithm. Finally, we compare the performance of both approaches on numerical simulations.
Open AccessMinimizing the Information Leakage Regarding High-Level Task Specifications
We consider a scenario in which an autonomous agent carries out a mission in a stochastic environment while passively observed by an adversary. For the agent, minimizing the information leaked to the adversary regarding its high-level specification is critical in creating an informational advantage. We express the specification of the agent as a parametric linear temporal logic formula, measure the information leakage by the adversary's confidence in the agent's mission specification, and propose algorithms to synthesize a policy for the agent which minimizes the information leakage to the adversary. In the scenario considered, the adversary aims to infer the specification of the agent from a set of candidate specifications, each of which has an associated likelihood probability. The agent's objective is to synthesize a policy that maximizes the entropy of the adversary's likelihood distribution while satisfying its specification. We propose two approaches to solve the resulting synthesis problem. The first approach computes the exact satisfaction probabilities for each candidate specification, whereas the second approach utilizes the Fr\'echet inequalities to approximate them. For each approach, we formulate a mixed-integer program with a quasiconcave objective function. We solve the problem using a bisection algorithm. Finally, we compare the performance of both approaches on numerical simulations.
- Open Access
Unpredictable Planning Under Partial Observability
We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of a decision-maker's trajectories while guaranteeing the completion of a task expressed by a reward function. First, we prove that a decision-maker with perfect observations can randomize its paths at least as well as a decision-maker with partial observations. Then, focusing on finite-state controllers, we recast the entropy maximization problem as a so-called parameter synthesis problem for a parametric Markov chain (pMC). We show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of this pMC. Finally, we present an algorithm, based on a nonlinear optimization problem, to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In numerical examples, we demonstrate the proposed algorithm on motion planning scenarios.
Open AccessUnpredictable Planning Under Partial Observability
We study the problem of synthesizing a controller that maximizes the entropy of a partially observable Markov decision process (POMDP) subject to a constraint on the expected total reward. Such a controller minimizes the predictability of a decision-maker's trajectories while guaranteeing the completion of a task expressed by a reward function. First, we prove that a decision-maker with perfect observations can randomize its paths at least as well as a decision-maker with partial observations. Then, focusing on finite-state controllers, we recast the entropy maximization problem as a so-called parameter synthesis problem for a parametric Markov chain (pMC). We show that the maximum entropy of a POMDP is lower bounded by the maximum entropy of this pMC. Finally, we present an algorithm, based on a nonlinear optimization problem, to synthesize an FSC that locally maximizes the entropy of a POMDP over FSCs with the same number of memory states. In numerical examples, we demonstrate the proposed algorithm on motion planning scenarios.
- 12 June 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 65 (4) , 1552-1567
Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints
We study the problem of synthesizing a policy that maximizes the entropy of a Markov decision process (MDP) subject to a temporal logic constraint. Such a policy minimizes the predictability of the paths it generates, or dually, maximizes the exploration of different paths in an MDP while ensuring the satisfaction of a temporal logic specification. We first show that the maximum entropy of an MDP can be finite, infinite or unbounded. We provide necessary and sufficient conditions under which the maximum entropy of an MDP is finite, infinite or unbounded. We then present an algorithm which is based on a convex optimization problem to synthesize a policy that maximizes the entropy of an MDP. We also show that maximizing the entropy of an MDP is equivalent to maximizing the entropy of the paths that reach a certain set of states in the MDP. Finally, we extend the algorithm to an MDP subject to a temporal logic specification. In numerical examples, we demonstrate the proposed method on different motion planning scenarios and illustrate the relation between the restrictions imposed on the paths by a specification, the maximum entropy, and the predictability of paths.
- 12 June 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 65 (4) , 1552-1567
Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints
We study the problem of synthesizing a policy that maximizes the entropy of a Markov decision process (MDP) subject to a temporal logic constraint. Such a policy minimizes the predictability of the paths it generates, or dually, maximizes the exploration of different paths in an MDP while ensuring the satisfaction of a temporal logic specification. We first show that the maximum entropy of an MDP can be finite, infinite or unbounded. We provide necessary and sufficient conditions under which the maximum entropy of an MDP is finite, infinite or unbounded. We then present an algorithm which is based on a convex optimization problem to synthesize a policy that maximizes the entropy of an MDP. We also show that maximizing the entropy of an MDP is equivalent to maximizing the entropy of the paths that reach a certain set of states in the MDP. Finally, we extend the algorithm to an MDP subject to a temporal logic specification. In numerical examples, we demonstrate the proposed method on different motion planning scenarios and illustrate the relation between the restrictions imposed on the paths by a specification, the maximum entropy, and the predictability of paths.