The ever-increasing presence of autonomy in our lives calls for immediate and significant investment in the development of effective, safe, and trustworthy autonomous systems. In the real world, these systems need to make sequential decisions in complex and dynamic environments while interacting with human decision-makers. Furthermore, they may have access to an immense amount of heterogeneous data, which requires them to be selective about what data to gather due to their limited perception capability. I focus on developing theory and algorithms that enable autonomous agents to operate in our complex world. The algorithms I develop address the following fundamental challenges: 1) active identification and gathering of actionable information from large-scale, multi-modal, and noisy data, 2) planning and learning based on partial and evolving knowledge, in real time and with theoretical performance guarantees, and 3) interacting and collaborating with humans in a trustworthy manner. Given the multidimensionality of these challenges, the proposed algorithms rely on drawing new connections between the fields of control, learning, formal methods, and information theory. The first part of my contributions entails introducing joint active perception and planning algorithms in unknown or uncertain environments so that a decision-maker can efficiently find the most relevant data for its task. In the second part of my contributions, I propose online planning algorithms capable of integrating runtime data, from the environment or a human user, into sequential decision-making reliably. The third part of my contributions presents planning algorithms for tasks described in temporal logic languages such that their outputs are interpretable by human users. The proposed interdisciplinary ideas enhance the efficiency, reliability, and interpretability of automated sequential decision-making — taking a step toward designing competent, autonomous systems that co-exist with humans.