Inclusion Criteria:

          -  Patients must be assigned to S1900C. Assignment to S1900C is determined by the LUNGMAP
             protocol genomic profiling using the FoundationOne assay. Biomarker eligibility for
             S1900C is based on the identification of a pathogenic somatic mutation in STK11 or
             STK11 bi-allelic loss on tumor

          -  Patients must have histologically or cytologically confirmed stage IV or recurrent
             non-squamous, mixed squamous/non-squamous (e.g., adeno-squamous carcinoma), or
             non-small cell lung cancer not otherwise specified (NSCLC NOS). Patients with pure
             squamous cell carcinoma are not eligible

          -  Patients with evidence of chronic hepatitis B virus (HBV) infection must have
             undetectable HBV viral load on suppressive therapy within 28 days prior to sub-study
             registration

          -  Patients with a history of hepatitis C virus (HCV) infection must have been treated
             and cured. Patients with HCV infection who are currently on treatment must have an
             undetectable HCV viral load within 28 days prior to sub-study registration

          -  Patients with known human immunodeficiency virus (HIV) infection are eligible,
             provided they are on effective anti-retroviral therapy and have undetectable viral
             load at their most recent viral load test and within 6 months prior to sub-study
             registration

          -  Patients must have received at least one line of anti-PD-1 or anti-PD-L1 therapy for
             stage III, IV or recurrent disease. Any number of additional, non-platinum-based
             chemotherapy or targeted therapy regimens for recurrent or metastatic disease are
             allowed

               -  Patients may not have received more than one line of anti-PD-1 or anti-PD-L1
                  therapy in the Stage IV or recurrent setting. Anti-PD-1 or anti-PD-L1 therapy may
                  have been given alone or in combination with platinum-based chemotherapy, an
                  anti-CTLA4 therapy, or other immune-modulatory therapy. Patients must have
                  experienced disease progression > 42 days following initiation (cycle 1 day 1) of
                  the anti-PD-1 or anti-PD-L1 containing regimen

               -  Patients who did not receive anti-PD-1 or anti-PD-L1 therapy in combination with
                  platinum-based chemotherapy, must have also received prior platinum-based
                  chemotherapy and experienced disease progression > 42 days following initiation
                  (cycle 1 day 1) of platinum based chemotherapy

               -  Patients who received anti-PD-1 or anti-PD-L1 therapy following concurrent
                  chemoradiation for stage III disease as their only line of anti-PD-1 or
                  anti-PD-L1 therapy, are eligible if they experienced disease progression less
                  than (<) 365 days from the date of initiation of anti-PD-1 or anti-PD-L1 therapy

          -  Patients who received prior adjuvant platinum-based therapy post-surgical resection
             for stage I-III disease (i.e. the patient has not received platinum-based chemotherapy
             for Stage IV or recurrent disease) must have had disease progression during or after
             platinum-based chemotherapy that occurred less than (<) 365 days from the last date
             that the patient received that therapy

          -  Patients must be able to swallow capsules whole

          -  Patients must not have had prior exposure to any agent with a PARP inhibitor (e.g.,
             veliparib, olaparib, rucaparib, niraparib, talazoparib) as its primary pharmacology

          -  Patients must not be taking, nor plan to take while on protocol treatment strong
             P-glycoprotein (P-gp) inhibitors (e.g. dronedarone, quinidine, ranolazine,
             itraconazole, ketoconazole), P-gp inducers (rifampin, ritonavir, tipranavir), or
             strong breast cancer resistance protein (BCRP) inhibitors (e.g. elacridar)

          -  Patients must have progressed following their most recent line of therapy

          -  Patients must not have received any prior systemic therapy (systemic chemotherapy,
             immunotherapy or investigational drug) within 21 days prior to sub-study registration.
             Patients must have recovered (=< grade 1) from any side effects of prior therapy.
             Patients must not have received any radiation therapy within 14 days prior to
             sub-study registration

          -  Patients must not be planning to receive any concurrent chemotherapy, immunotherapy,
             biologic or hormonal therapy for cancer treatment while receiving treatment on this
             study. Concurrent use of hormones for non-cancer-related conditions (e.g., insulin for
             diabetes and hormone replacement therapy) is acceptable

          -  Patients must have measurable disease documented by computed tomography (CT) or
             magnetic resonance imaging (MRI). The CT from a combined positron emission tomography
             (PET)/CT may be used to document only non-measurable disease unless it is of
             diagnostic quality. Measurable disease must be assessed within 28 days prior to
             sub-study registration. Pleural effusions, ascites and laboratory parameters are not
             acceptable as the only evidence of disease. Non-measurable disease must be assessed
             within 42 days prior to sub-study registration. All disease must be assessed and
             documented on the Baseline Tumor Assessment Form. Patients whose only measurable
             disease is within a previous radiation therapy port must demonstrate clearly
             progressive disease (in the opinion of the treating investigator) prior to sub-study
             registration. CT and MRI scans must be submitted for central review via Transfer of
             Images and Data (TRIAD)

          -  Patients must have a CT or MRI scan of the brain to evaluate for central nervous
             system (CNS) disease within 42 days prior to sub-study registration. Patient must not
             have leptomeningeal disease, spinal cord compression or brain metastases unless: (1)
             metastases have been locally treated and have remained clinically controlled and
             asymptomatic for at least 14 days following treatment, and prior to sub-study
             registration, AND (2) patient has no residual neurological dysfunction and has been
             off corticosteroids for at least 24 hours prior to sub-study registration

          -  Patient must not have had a major surgery within 14 days prior to sub-study
             registration. Patient must have fully recovered from the effects of prior surgery in
             the opinion of the treating investigator

          -  Serum bilirubin =< institutional upper limit of normal (IULN) (within 28 days prior to
             sub-study registration). For patients with liver metastases, bilirubin must be =< 5 x
             IULN

          -  Either alanine aminotransferase (ALT) or aspartate aminotransferase (AST) =< 2 x IULN
             within 28 days prior to sub-study registration (if both ALT and AST are done, both
             must be =< 2 IULN). For patients with liver metastases, either ALT or AST must be =< 5
             x IULN (if both ALT and AST are done, both must be =< 5 x IULN)

          -  Patients must have a serum creatinine =< the IULN or calculated creatinine clearance
             >= 50 mL/min using the following Cockcroft-Gault formula. This specimen must have been
             drawn and processed within 28 days prior to sub-study registration

          -  Patients must have Zubrod performance status 0-1 documented within 28 days prior to
             sub-study registration

          -  Patients must not have any grade III/IV cardiac disease as defined by the New York
             Heart Association Criteria (i.e., patients with cardiac disease resulting in marked
             limitation of physical activity or resulting in inability to carry on any physical
             activity without discomfort), unstable angina pectoris, and myocardial infarction
             within 6 months, or serious uncontrolled cardiac arrhythmia

          -  Pre-study history and physical exam must be obtained within 28 days prior to sub-study
             registration

          -  No other prior malignancy is allowed except for the following: adequately treated
             basal cell or squamous cell skin cancer, in situ cervical cancer, adequately treated
             stage I or II cancer from which the patient is currently in complete remission, or any
             other cancer from which the patient has been disease free for five years

          -  Absolute neutrophil count (ANC) >= 1,500/mcl (obtained within 28 days prior to
             sub-study registration). Patients must be transfusion independent (i.e., no blood
             product transfusions for a period of at least 14 days prior to sub-study registration)

          -  Platelet count >= 100,000 mcl (obtained within 28 days prior to sub-study
             registration). Patients must be transfusion independent (i.e., no blood product
             transfusions for a period of at least 14 days prior to sub-study registration)

          -  Hemoglobin >= 9 g/dL (obtained within 28 days prior to sub-study registration).
             Patients must be transfusion independent (i.e., no blood product transfusions for a
             period of at least 14 days prior to sub-study registration)

          -  Patients must agree to have blood specimens submitted for circulating tumor DNA
             (ctDNA)

          -  Patients must also be offered participation in banking and in the correlative studies
             for collection and future use of specimens

        Exclusion Criteria:

          -  Patients must not be pregnant or nursing. Women/men of reproductive potential must
             have agreed to use an effective contraceptive method. A woman is considered to be of
             "reproductive potential" if she has had menses at any time in the preceding 12
             consecutive months. In addition to routine contraceptive methods, "effective
             contraception" also includes heterosexual celibacy and surgery intended to prevent
             pregnancy (or with a side-effect of pregnancy prevention) defined as a hysterectomy,
             bilateral oophorectomy or bilateral tubal ligation. However, if at any point a
             previously celibate patient chooses to become heterosexually active during the time
             period for use of contraceptive measures outlined in the protocol, he/she is
             responsible for beginning contraceptive measures

          -  Patients must not have a history of prior organ transplantation, including allogeneic
             stem-cell transplantation

          -  Patients must not have received systemic treatment with corticosteroids (> 10 mg daily
             prednisone or equivalent) or other immunosuppressive medications within 7 days prior
             to sub-study registration. Inhaled or topical steroids, and adrenal replacement doses
             =< 10 mg daily prednisone or equivalent are permitted in the absence of active
             autoimmune disease

          -  Patients must not have active autoimmune disease that requires systemic steroids
             (equivalent of > 10 mg of prednisone) or immunosuppressive agents within 7 days prior
             to sub-study registration (for example disease-modifying anti-rheumatic drugs).
             Exceptions include: patients with controlled type 1 diabetes mellitus, controlled
             hypo- or hyperthyroidism, vitiligo, resolved childhood asthma/atopy, or psoriasis not
             requiring immunosuppressive therapy

          -  Patients must not have any impairment of gastrointestinal function or gastrointestinal
             disease that may significantly alter the absorption of talazoparib (e.g., ulcerative
             disease, uncontrolled nausea, vomiting, diarrhea, malabsorption syndrome, small bowel
             resection, or active peptic ulcer disease). Patients must not have active small or
             large intestine inflammation such as Crohn's disease or ulcerative colitis within 12
             months prior to sub-study registration

          -  Patients must not have known prior or suspected hypersensitivity to monoclonal
             antibodies (grade >= 3)

          -  Patients must not have any history of anaphylaxis or uncontrolled asthma. Uncontrolled
             asthma is defined as a patient having any one of the following criteria:

               -  Poor symptom control: Asthma Control Questionnaire (ACQ) consistently > 1.5 or
                  Asthma Control Test Questionnaire (ACT) < 20 (or "not well controlled" by
                  National Asthma Education and Prevention Program [NAEPP] or Global Initiative for
                  Asthma [GINA] guidelines over the 3 months or evaluation)

               -  Frequent severe exacerbations: 2 or more bursts of systemic corticosteroids (CSs)
                  (> 3 days each) in the previous year

               -  Serious exacerbations: at least one hospitalization, intensive care unit stay or
                  mechanical ventilation in the previous year

               -  Airflow limitation: Forced expiratory volume in 1 second (FEV1) < 80% predicted
                  (in the presence of reduced FEV1/forced vital capacity [FVC] defined as less than
                  the normal lower limit) following a withhold of both short- and long-acting
                  bronchodilators

          -  Patients must not have experienced any immune related adverse event, including
             pneumonitis that led to permanent discontinuation of prior immunotherapy and/or
             required prolonged high dose of steroids

          -  Patients must not have evidence of active infection requiring systemic therapy

          -  Patients must not have received any live attenuated vaccinations within 28 days prior
             to sub-study registration